Why was Avimelech Chayav Misah? He had not been warned!
Chizkuni (citing Midrash Rabah): From here we see that a ben No'ach does not require warning.
Or ha'Chayim: Hashem was warning Avimelech that he would be Chayav Misah if he retained Sarah. 1
Seforno: This is not referring to the death-sentence, but to the blocking of all orifices, which had already begun and which would result in death, unless Avimelech returned Sarah and Avraham Davened on his behalf, as the Pasuk goes on to explain.
Makos 9b: A Nochri is Chayav Misah for not having learned that when visitors come, we ask about food for them, and not about their women. 2
Why was Avimelech punished less than Pharaoh?
Moshav Zekenim (Bereishis 12:17): Initially Pharaoh was Shogeg, but later he was Mezid after Hashem told him that she is Avraham's wife.
Riva: Also Avimelech was stricken; all openings were closed. There is no source to say that Pharaoh was stricken more.
Why did Hashem warn Avimelech before punishing him, unlike Pharaoh?
Moshav Zekenim: Hashem knew that he was a Tzadik and he would heed the warning. Pharaoh would not; had Hashem not made him a Tumtum, he might have blemished Sarah. Also, Avimelech took her honorably, through nobles, and in the way of marriage - "va'Yishlach... va'Yikach." Pharaoh did not, for he already had a wife.