...though possibly Civ 5's traits are more exclusive [than in Civ IV]...
The leader traits are 100% unique for each civ and the main reason why each civ plays differently.
Example; Austria has the ability to marry City States. This means that once a City State is allied, Austria can for a sum of money make this City State a city of their own. No other civ can gain this ability at any part of the game.
Another one; Incan units can move on hills like it was flat terrain, and roads on hills cost them no maintenance. Again, only the Incans have this, and it makes playing them different.
Most civ's bonuses are bold and big, and for me they enrich the game. Much more than giving a % advantage to this or that end like a lot of games do.
[Religion] I thought should have been done in the original game. I felt religion was one of the best features to be added in Civ4, it just needs some improvement. I was also hoping on seeing Corporations expanded on to make trading more robust and dynamic, but those were cut too.
Again I need to apologise for not being familiar with Civ IV, but from what I've read I believe religion is very differently done between the games, perhaps to the extent that only the name 'religion' is the same. There are no political consequences at all to choosing a religion in Civ 5, it's just a neutral bonus system, mainly using terrain features, that happens to use terms like 'faith', 'belief' and 'missionaries'.
My disappointment in Civ 5 was with diplomacy and trade, and that still is a weak aspect of the game after Gods & Kings. Both religion and the espionage system haven't added much real intrigue. The developers of the game seem very wary of doing anything that enters the field of diplomacy. Possibly they're afraid the human player becomes too powerful with diplomatic tools, and they want to protect the AI from getting wrapped around the human player's finger.
It's not a matter of the game being objectively less complex and some people just preferring it simpler, but rather of people having different opinions as to what amounts to complexity.
Some things were objectively more complex in previous games. Just look at Civ III's system of trade routes and reputation, like for example how a broken trade route would affect your reputation with a civ, depending on the diplomatic situation. There were a lot more dependencies in that game.
My guess is that the developers thought things were getting too complex, and I know a lot of concepts in Civ III went over the head of casual players. It wasn't easy to understand how reputation worked, or war weariness, or why the value of techs and luxes could so fluctuate.
Although Civ 5 has complexity in other areas. The way how border expansion works is undeniably more complex in Civ 5 than it ever has been. How much that has added to strategic depth you could argue about, it's possibly mostly an aesthetic thing; making the border growth of cities look more organic. It will have been more complex to make it this way than to play with it.
The rule in Civ 5 is still that things have a fixed value; things like luxes and and research agreements come at fixed prices, with just a basic adjustment here and there. Although with some things it looks like the developers are starting to refine things more again, like with the time it takes a spy to gather intelligence. Also the promised trade routes seem to bring in more dependencies again.
What is good to note in a discussion like this is that the developers are listening to the fans of the game. There are plenty examples of them responding to what we are saying. If there's a strong message coming from us that we find the game too simple, they'll go thinking about how they can bring back some complexity.