I somewhat agree with Quintillus. I don't believe there should be any leaders in the traditional Civ sense, where you pick one leader at the start, with or without unique traits, and that's your character for the rest of the game.
What I'd like to see instead are leaders that change over time and in response to player actions. Starting out as Rome, you'd get somebody like Cincinnatus for example, and as time progresses this would change to the Gracchi or Sulla and then finally to the Caesars, if your government changed from republic to empire. Switching to communism in Russia would see Lenin and Stalin take power from Czar Nicholas, and similarly with China and Mao. Under democracies some sort of election might even determine it, along with political parties.
This would not have to be purely for flavor, as different leaders could still have different priorities (militarist Stalin vs. pacifistic Gandhi) and possibly even different trait bonuses. But for it to work, the 3D artwork for every leader would have to be abandoned in favor of 2D or photographs as in Civ 2, since it would be too demanding on the developers, and I don't think they're willing to go that direction.