Leaders I'd like to see instead of old, tired ones...
England - Queen Victoria (and Redcoat unit)
Rome - Marcus Aurelius/Hadrian (cultural bias) or Traian (expansive bias)
Germany - Frederick the Great
France - Louis XIV or Henrique IV
Greece - Pericles
Mongolia - Kubilai Khan
Persia - Nader Shah (of Islamic era btw, not Achaemenid - unique unit Qizilbashi)
Portugal - Henrique the Navigator (exploration bias)
Spain - Philippe II
Russia - Empress Elizaveta Petrovna (ruled succesfully in years 1740 - 1762, "she remains one of the most popular Russian monarchs due to her strong opposition to Prussian policies and her decision not to execute a single person during her reign" - interesting divergence from boring civ cliche of "brutal russia")
Netherlands - Queen Wilhelmina
India - anybody but Gandhi

there are many male emperors such as Chandragupta Maurya, Ashoka, Shivaji Bosle, as well as female heroines/queens such as Lakshmibai...
Arabs -
Shajar al-Durr would be amazing. She was of the same dynasty as Saladin, one of very few powerful queens in Arab history, repelled Seventh Crusade on Egypt, and Arab female leader would be
very interesting.
Ottomans - Roxolana. Well Roxolana would be very unorthodox choice... but she is no more inappropriate as Ottoman ruler than Theodora as Byzantine one

More conservative choice: Mehmed II
Aztecs - Tlacaelel
Zulu - Cetshwayo (although I'd prefer no Zulu at all

)
Ethiopia - emperor Gelawdewos (defender against Adal-Ottoman alliance) or Menelik (defender against Italians)
Korea - Queen Seondeok
Maya, Inca, Brazil, Babylon, Indonesia, Byzantium - I have no competence to speak for them (and yes I think they will all return)