The differences don't make for radically different games so much as different strategies to achieve the same things. I find with Organised leaders (Asoka, Zara Yaqob - or as I know, Citroen Xsara Picasso - and Julius Caesar) you can sprawl better and therefore do better on land-based maps; on sea-based maps go for a Financial leader because each coast tile produces three coins instead of two and you can support your empire better overall.
There ought to be more differences between handicaps or bonuses for each civ; the AI will be reasonably historically correct (e.g. I played with Choose Religions once and the AI Isabella, who founded the first religion, naturally went for Christianity) and I would go further and impose handicaps and bonuses on religions but I can see why that will never catch on (for example my idea would have Judaism give a bonus to commerce but not be permissible as a state religion, for example; despite Israel and ancient Judah the Jews - and my Jewish OH said this, by the way - have never managed to keep a state together for long) given sensitivities. It's in Civ Revolutions that different cultures have significant benefits and handicaps so I foresee this happening in Civ 5 unless Sid wants to keep the console game going in one direction and the PC version in another.
But I think you underestimate the appeal of Civ 4 and if you think things are a little boring you have not yet tried Beyond the Sword. Again I'd expand the range of quests and random events, but they keep you on your toes.