I assume they will either want to represent different aspects of the culture (ie. Athens v. Sparta) or different time periods (ie. Gandhi v. Chandragupta) or both. This being VI, they may want leaders who haven't been done before, unless it's a big enough name to guarantee sales.
Egypt - they have a classical queen, so I'd expect an ancient king. Ramses is obvious. Akhenaten is a big personality and might be eclectic enough to be interesting. Khufu, Amenhotep III and Thutmose III are also good possibilities.
Rome - they have one of the "good" emperors, so I'd expect either a consul of the republic or a "bad" emperor. Julius and Augustus Caesar are of course too obvious. Scipio and Cicero are good republic picks. Marcus Aurelius is famous but wouldn't play all that differently from Trajan. Finally, Caligula, Nero, etc. are big personalities and would represent a whole other side of Rome.
China - they have the first emperor. Probably not Mao due to modern sensibilities with the Chinese market. (They had to remove Mao and make a custom Taizong leader just for Chinese players in Civ4.) Wu Zetian is a good counterpoint to Qin. Taizong is another good choice that hasn't really been seen in the western markets much (unless you count CivRev2). Yongle/Zhu Di also has a lot of fans. Kangxi too. And of course, everybody is infatuated with the 3 Kingdoms period (it's even getting it's own Total War game) so there's Cao Cao the warlord. A very different playstyle from Qin.
America - they have a late industrial/early modern president. I guess there's always Lincoln, though he's not that far off from TR and has been done to death. FDR is not likely since they probably don't want exclusively Roosevelt presidents. I bet they'll go colonial; either Washington or perhaps Jefferson, who hasn't been done before.
England - Elizabeth is a big name, though she might not play all that differently from Vicky. Henry VIII would play very differently. So would Alfred the Great. If they want to complete their 3rd Crusade collection of leaders, then Richard I is a must, though we've almost reached a supersaturation of medieval leaders and he could barely speak English, if at all. I wouldn't like it if they went with Oliver Cromwell or Winston Churchill, but that's just me.
France - They need to get this one right, since Catherine was a controversial choice. Louis XIV is the obvious pick, though Napoleon has his fans. Richelieu would be unconventional but interesting. Joan of Arc would be another controversial pick that might set people off, so I don't think she's likely this time. Going back to the 3rd Crusade motif, they'd need Philip Augustus.
Germany - I don't think they really need one, since Barbarossa was the perfect choice. Bismarck is an obvious counterpart though -- an industrial era Chancellor opposite a medieval emperor.
Russia - they have a progressive emperor in Peter, maybe they'll go with a reactionary leader like Ivan IV. He'd be crazy.
Soviets are controversial. I doubt we'll see Stalin. Lenin is a little more likely, but not by much. Catherine was extremely popular. They could bring her back if they differentiate her enough from the French Catherine.
Japan - very hard to say. They obviously won't want another Shikken. Emperors are out because it's sacrilege to depict them this way in Japan, despite how much everyone would want Meiji. Queen Himiko is technically not an Emperor/Empress and would be a rare female leader for Japan, but she's semi-mythical. That leaves a bunch of Shoguns. Minamoto no Yoritomo hasn't been done yet, but he may be too close chronologically to Hojo. The Sengoku leaders are always popular: Oda Nobunaga and Tokugawa Ieyasu. They'd have to be more aggressive than Hojo though.
The Sumerians don't just need an alternate leader; they need an entire redesign. (But yeah, Gudea and Ur-Nammu, in that order, would be my preferred choices for Sumer.)
german leader 
