America: People have mentioned FDR, JFK, Teddy Roosevelt and Lincoln, who I think are all excellent choices, but I would like to add, just to have something of my own here,
Woodrow Wilson. His traits should reflect his character as an intellectual and an idealist, for instance I think he should emphasize building relations, protecting and allying with city-states as well as focus construction on buildings that benefit research perhaps.
Arabia: I always disagreed with Saladin as a leader for the Arabs in Civ IV, to start with he was a Kurd, he was ruler of a state with its heart in Egypt, and the political and military elites in his empire were mostly Kurds and Turks. I'd possibly have agreed with him as a leader for Egypt though, but I will get back to that. I think
Feisal (of the Hashemite dynasty) would make an interesting Arab leader. He was one of the early champions of pan-Arab nationalism and were it not for the British and French cutting up the Middle East between them he could potentially have become the ruler of an Arab state encompassing Iraq, Syria and Arabia. I am also a proponent of, if Civ V is to eventually include new and alternative leaders, the different leaders representing different eras in that nation's history.
Aztecs: Though Montezuma II is the most famous Aztec emperor among most people who have heard of the Aztec empire, I have never felt like he quite cuts it. He does not seem to have been a very competent leader at all, mostly insecure and controllable. The first Montezuma (though the name is more accurately spelled Motecozuma) was a more capable ruler and I also understand the last emperor Cuahtemoc is remembered quite fondly in Mexico. Which brings me to the thought that perhaps its a bit unfortunate that this civilization is known as 'the Aztec empire' which severly limits the time scope from which one can choose a leader. One would gain a lot more choices by it being the called the Mexican empire (remember the Aztecs called themselves 'Mexica'), though I am given to understand that some might not take that very seriously. One could then have leaders such as
Emiliano Zapata (though he never led the country, but neither did Ghandi!) who could offer Aztec/Mexican players the alternative of a leader from an era different from that of Montezuma II.
China: For China I propose that
Kublai Khan would be a good choice for a leader (yes, he was a Mongol, but he ruled over China, and Saladin was a Kurd). Under his rule China, again (though in the guise of a Mongol empire), became a great expansionist power, ruling Tibet, Eastern Turkestan, Korea and mounting two great (though ill-fated) invasions of Japan. IIRC it was also under his rule that paper money first was used.
Egypt: Keeping in line with my preference for different leaders to represent different eras in history I will jump about 3000 years into the future from Ramesses II and suggest
he is often regarded as the founder of modern Egypt (though he was by no means an Egyptian nationalist, he was Albanian and was greatly influenced by the British rule in India for his ruling of Egypt, entrusting most important positions to Turks and Albanians whom he felt were more accustomed and able to rule). Under his rule Egypt achieved de-facto independence from the Ottoman Empire and he carried out reforms of Egypt's military and economy, turning the country around.
England: I strongly agree with those who mentioned Churchill and (someone must have mentioned) Victoria as new English leaders. While I think either of those two are supremely fitting of leading England in a possible (or hypothetical) expansion of Civ V, the fact that Longbowmen are England's UU got me thinking of Agincourt, and Henry V. A very shakespearean and militarily minded Henry V might make for an interesting Civ leader.
Chose the picture from Kenneth Branagh's Henry V film adaptation, because I was mostly thinking of that
France: I don't really have any obvious new suggestions here, people have already mentioned Louis XIV, and De Gaulle (or if not, he was at least in Civ IV). It would perhaps be benefitial to have a medieval or renaissance era French leader, but I couldn't really think of anyone who's well known enough. I got thinking of Marianne, the French national symbol, though that would be a bit like Uncle Sam leading America (which would have been silly, but completely awesome).
Germany: I'm in somewhat the same situation regarding Germany as with France. I already think Bismarck is perfect, and people have already mentioned Charlemagne and Hitler (though I actually don't think he should be in). One could of course include Frederick of Prussia again though (must also have been mentioned).
Greece: Should really be named Hellenic Empire I think, because Alexander wasn't Greek (though he and the Macedonians largely adopted Hellenic culture) and Greece as a nation has never really been an empire or a powerful unified nation. Here I will break my rule of having leaders from different eras and suggest, as others undoubtedly have,
Pericles as an alternative leader for (what I think should be called) the Hellenic Empire.
India: Seeing as India's UB is a Mughal fort, I quickly came to the conclusion that a natural alternate leader for India would be one of the Mughal rulers. Because of the iconic status of the Taj Mahal I think
Shah Jahan (the guy who ordered it built) would be a good choice. As a Mughal he would also represent an interesting counterpart to Ghandi (being the leader of a a dynasty founded on conquest and horseback warriors).
Iroquouis: Unfortunately I don't know enough about them to make an educated suggestion/wish, something I shall have to remedy.
Japan: It has been mentioned that Japanese do not like their emperors being depicted, which rules out Meji (who by the way was one of the only emperors to have wielded real power in almost a 1000 years). Though I had someone else in mind
Kato Takaaki. He was foreign minister of Japan during WWI during which he was greatly influential in the country's entry into the war and it was his policies that enabled Japan to show how a country could gain the most from war while paying as little a price as possible. He's not as iconic as the other leaders, but I think he's an interesting individual, this quote pretty much sums it up;
"Of all the world's statesmen in 1914, Katō proved the most adroit at using war for the purposes of policy. Domestically he exploited it to assert the dominance of the Foreign Ministry and of the cabinet in the making of Japan's foreign policy. Internationally he took the opportunity to redefine Japan's relationship with China. In doing so he was not simply outflanking the extremists opposed to him; he was also honouring his own belief that Japan should be a great power like those of Europe."
Ottomans: Should really be called 'the Turkish empire' (would also fit in with the other civs, as they have more generic names) as that would justify including Atatürk, who is as iconic a leader as can possibly have existed. Though a possible interesting Ottoman leader could be
Mahmud II. His rule marked the beginning of the Ottoman attempts to modernize their army, society and government called the Tanzimat (which I believe was mostly halted by the tyrannical Abdulhamid II), he oversaw the destruction of the Janissary corps and the first true modernization of the army.
Persia: This was one of the first one to have been obvious to me.
Shah Abbas I. He made Persia a great empire once more, a great rival of the Ottoman Empire and established trade and treaties with European nations, and he built the new splendid imperial capital, Isfahan.
Rome: Augustus is just too perfect. Too perfect. His perfectness blots my mind.
I'm getting bored with writing now and I have mostly said what I wanted except that I'd think Ivan the Terrible would be a cool Russian leader.