Actually, perhaps even better than MOO2 style "mercenary" heroes, would be if heroes appeared like the "Great People" in Civ4 based on points earned by an empire, but then the heroes could also be renamed by the player or at least have names selected from a list based on the empire that spawned them and their role!
So if you're using a Klingon shipset, your military heroes might get names like Kahless and Kor, but if you're playing as, oh, I dunno, the Polish Revivalist Dominion (hehe, anyone get the reference?) you might get heroes like Walesa (a political leader) and Wojtila (a religious leader)
Of course the Klingons would have political and religious leaders, and the Poles would have military leaders - I just can't think of any names at the moment :P