I think all civilizations should have at least two leader options and two unique units.
If we expect Firaxis to add new civilizations in future expansions, I think we need to identify eligibility criteria. These are: (1) should be either nostalgic or interesting, (2) should not pose political problems (hence no Israel or Armenia), or (3) should be new.
The alternate American leader would inevitably be George Washington or Abraham Lincoln. I’m not in love with the idea of the P-51 Mustang as the unique unit. I think that the Minuteman, Sherman tank, or aircraft carrier would have been more iconic.
Arabia’s alternate leader could potentially be King Faisal I (of Lawrence of Arabia fame), but Zenobia is a female option and possibly better-known. I honestly don’t know that there’s a more iconic option for an Arabian military unit than the Mameluke. Possibly the Assassin or the Camel Archer? The latter feels hopelessly stereotypical and somewhat generic, but at the same time seems to fit the bill given Arabia’s geography.
No idea what to do about the Aztecs. The Aztec Empire lasted less than one hundred years, and most players are apt to be unfamiliar with any leader other than Montezuma. Of course, that shouldn’t be a show-stopper. Same problem with the unique unit. Probably a better fallback is a unique tile improvement, the temple complex.
Egypt could do with Ramesses, or, if Firaxis is feeling especially bold, Gamal Abdul Nasser. Their second unit should be the Mamluk.
England needs the Longbowman more than it needs the Redcoat. Maybe a Henry for the other leader? If not him, then William the Conqueror or Richard the Lionheart.
For France, the second special unit might well be the French Foreign Legion. The other optional leaders would be the Sun King or Charles de Gaulle.
The decision to give Germany the U-Boat is an interesting one, but it works. Bismarck is the obvious second leader option, followed by Frederick the Great. I guess Landsknecht and Panzer were considered passe. The former could be brought back, with interesting results.
Greece needs Alexander back, along with Companion Cavalry.
I guess, for India, you could go the Ashoka route leader-wise. Maybe the Gorkha Regiment as a second special unit, although that could be compromised by the colonial overtones.
Japan could add one of the early Shogun as a leader. One option for special units is the Zero fighter. Another is the aircraft carrier. Both might be too on-the-nose, but they’ve gone the Zero route before.
No idea what to do with the Kongo.
No idea what to do with Norway. They got Ski Infantry in an earlier title. Sounds plausible to me.
Rome needs Caesar. Other than the Legion, the only other recognizable unit is the Trireme, but that market is cornered by Carthage. Possibly the Bolt-Thrower? I guess there’s the possibility of the Forum as a district, or even the Colosseum.
Russia could take Catherine to complement Peter. The Cossack could be supplemented by the T-34 tank. The Mig is another alternative.
In the absence of Portugal, Spain can take the Caravel along with the Conquistador. The obvious female Spanish leader option is Isabella. They could also gain the Tercio, although we are talking about units for the same era in that case. Spain and Portugal both need a trading fort building option, sort of like the Colony in Civilization III.
Sumeria also has a leader problem. And a special unit problem. Gilgamesh and the War-Cart hit the nail on the head.
Brazil gets Pedro II. I can’t think of a second leader that would be worthwhile. The Minas Geraes unit is an interesting one, reflecting the naval race of the late nineteenth and early twentieth centuries. It’s as viable, I think, as the Pracinha. However, I really liked the Brazilwood Camp, which I think should make a return as a district.
One civilization that might be worth bringing back for nostalgic value is the Carthaginians, with leaders Hannibal and Dido. Their special units would be the War Elephant (more iconic than the Sacred Band) and Qaudrireme or Quinquereme. Interestingly, Civilization III assigned Carthage the Numidian Mercenary, which is arguably less well-known than any of the other options. Give them some kind of lighthouse or trading colony special district.
The Koreans are another plausible addition, if only because South Korea has a reputation for computer gaming. The Hwacha, which appeared in Civilization III, still seems viable as a unique unit. If they go for a second, I’d say it should be the Turtle Ship.
The Khmer Empire showed up in Civilization IV, and it has novelty value, if nothing else.
For North America, both Canada and Mexico are options. Canada might make more sense because there are probably more Canadian players of Civilization than there are Mexican. The obvious Canadian unit is the Royal Northwest Mounted Policeman. The special building would be some kind of fishery or fur camp. Canada would go for a diplomatic win, I’d guess. Maybe Pearson and Trudeau (the Elder) for leaders? You could also go Montcalm or even opt for a First Nations leader.
I guess you do need to consider bringing the Persians, Mongols, and Babylonians back as a sop to old players who loved them. The Cherokee are also a good pick for a Native American civilization. I really like the Mali idea, which I guess hearkens back to Civilization 4. I think South Africa is out because of potential connections to Apartheid and the opportunity to revisit the Zulu, while Nigeria is out because the older African civilizations are geographically more inclusive.
In Europe, I think it’d be interesting for them to try Poland, complete with Hussar. If you do the Netherlands, they get the windmill and the merchantman, for sure.
The Byzantines probably have to go for Varangians and Kataphrakts, or else the Dromon. Give them Justinian and Theodora for rulers. The focus would be on Culture or economy.
The Khmer special unit in Civilization IV was the Ballista Elephant, which is just plain interesting. The Byzantines probably have to go for Varangians and Kataphrakts, or else the Dromon.
No idea what to do with the Ethiopians, except to give them the obelisk as a building and Menelik as their ruler.
The Portuguese would get Henry the Navigator and the caravel, plus possibly the fort. A really neat option would be to give them a special feature called the Black Ship, in homage to Shogun, a vessel that leaves one Portuguese port and travels to another, but can be intercepted along the way.
Civilization V also tried adding Sweden, which is also a fine option. Their special units were the Hakkapeliitta. And the Caroleans. For lack of a better option, I guess that one stays.
I'd love to see them try Latin Frankia, but I think that's out for political reasons, along with a personal favorite of mine, Yugoslavia.
Australia is probably a good market, but Oceana makes sense as a more encompassing civilization. Possibly add the ANZAC Corps as a second unit for Oceana? The other option is the Bush Camp. The Maori Warrior was a good option in the past and remains such. The oracle is a second option. Focus on exploration and culture sounds good, as you said.