Having multiple leaders wasn't a bad thing.
By itself it wasn't. But small civilization difference caused by civilization-leader separation was.
I don't feel that using 1 movement instead of 2 when you enter a forest does difference a civ more than having 3 commerce in tiles where you have 2 + generating 2 bonus culture in each city. For example.
The problem is what in Civ 4 civilizations are more generic. No funny specializations like Iroquois foresters, British navy or Songhai burn as it will be in Civ 5.
That's true. But I still think the specializations of civ5 have less impact than the traits.
Civ rev was already a big step from Civ 4.
But I do think that each civilization and it's leader had a lot more personality
Having Civs/leaders play a special way seems to make it far more predictable in how they will behave and surely that takes away some element of the challenge?