Civ IV has lots of good ideas, but they haven't be implemented evenly, and that hurts the game.
Consider the freebies for being the first to discover a Tech. Very nice: but because only a handful of techs give these bonuses, your tour through the Tech tree is going to be the same every time. The fix, I feel, is to remove UUs from nations and add them to the tech tree: eg if you are the first to research Guilds, you get a variant Knight (hopefully, of your choice). Many early UUs are only useful in unusual situations (frex, Jaguar is great if you don't have iron, useless otherwise) so this would allow you to select them when needed. Also, if a tech renders a wonder obsolete, this shouldn't occur if *you* are the first to develop that tech.
Unit promotions look cool, and if you never enter combat, you can happily waste time tinkering with your favourite units. But so what? In Civ III, a guy with pointy stick could kill a tank. In Civ IV, a guy with a pointy stick can kill a carefully upgraded tank. So why bother?
Combat is far too random, and improvements in weaponry have only minimal effect. The basic tactic in Civ III - rely heavily on fast units - has been nobbled by crippling the ability to withdraw. So everybody uses SoDs, because there's no alternative. So the designers have added completely unhistorical siege units as stack killers: so we build stacks of catapults!
Ridiculous.
One obvious fix: units get a huge bonus when fighting opponents who don't have the tech needed for building them: this reflects the shock value of the new weapons. Historically, elephants have only been effective in these circumstances. However, every battle against the new unit type should give beakers towards the new tech, to reflect captured weapons/seeing the units in action/defectors etc. And yes, this should allow access to techs that you don't have the pre-reqs for!
Adding religion was a good move; it is one of humanity's primary obsessions. It is handled in a wussy PC fashion, but if they hadn't, they'd have been sued off the face of the earth. So we should be grateful for what we've got, I guess. The thing with religions is that:
a) they aren't the same, or even similar. A Jewish or Christian democracy looks nothing like a Islamic theocracy and neither look anything like a Buddhist military dictatorship.
b) most 'new' religions are old religions that have crossed national boundaries. Christianity has become the world's most successful Jewish sect by spreading amongst non-Jews. Islam (and other forms of Arianism) occurred when garbled ideas of Christianity spread into the barbarian world. Buddhism is dodgy Hinduism for non-Indians.
Now, (b) could be coded! When a religion spreads across a border, give it a (high) chance of mutating into something unrecognisable by the home country. That would encourage deliberate seeding of your pet religion by missionaries to prevent heresies.
I like the idea of gaining military knowledge through combat with higher tech units...Also, the UU is a cool idea, but unfortunately some of the UU's are just not nearly as useful as some. The UB aspect is more imba IMO...some are just awesome, like the HRO or as I've found out this past game the Portuguese Feitorias. I'd like to see what the Dutch UB for levee does and how imba that is.