Why do people keep talking about Cleopatra? She isn't in the game, for which I am glad. Hatshepsut is not Cleopatra.
Hatshepsut: b.~1530 BC - d.1482 BC
Cleopatra: b.69 BC - d.30 BC
Almost 1,500 years separate the two.
Furthermore Hatshepsut was one of the best Pharoahs Egypt had. She is one of the few female figureheads in Civ IV that can be seen as being there without any need for PC considerations. Her acheivements make her fully worthy of being there. Just because somebody is a woman does not mean they didn't do things making them worthyof being included in the game.
Now...
They should have done two Egyptian leaders (I suspect that we'll see some existing Civs get additional leaders in expansions). I think that Khufu and Ramses II are the most obvious choices for the second (can we have more than two?) leaderhead for Egypt. No Greeks.
For the Persians I'd say Darius, except that his rule and traits would be so similar in game terms to Cyrus. Given that I'd go with Xerxes.
For Greece I think Pericles would be the way to go after the obvious Alexander.
For Rome I'd rather they hadn't used Julius Caesar (for all those saying Churchill could be used because he wasn't the technical ruler, well, Julius Cesaer never was thechnically ruler either) and had used Augustus Caesar to represent the Empire and Lucius Junius Brutus to represent the Republic.