1. a harder AI, with less free advantages
Self explanatory.
2. many more types of governments and less anarchy
For one, there should be no useless goverments like communism is now. It would also be nice if you couldn't classify goverments as "this one is the best gov for science, this one is good for war". With the way we have it now there is always a clear absolute best goverment given what you want to do. Nothing wrong with that, but it could be more interesting.
I would also like to see more decentralized feudal and city state governments in the ancient/medieval era and less anarchy in general. Anarchy should be reserved for changes into oppresive governments/dictatorships and not, for example, changing from a capitalist to a socialist government.
As a smaller point, I think we should finally have a civ game where democracy refers to the Greeks. Also, there needs to be a difference between ancient and modern forms of goverments that are currently called the same thing. The Roman's republic ain't exactly our good old American republic you know (not too mention the many other different types in the free world today.)
3. Less cheesy diplomacy/trading.
First of all, the way we have it now reputation is too binary. It also is stupid that unless an AI refuses to sell/buy something it will always have a price in gold. Every game civs cripple themselves one after another with zero gpt because they are constantly buying luxuries and techs they shouldn't buy. They continue to cripple themselves because they are willing to put a gold price on everything, including being in last place.
In addition to reputation and attitude, there needs to be a third level of relations: "friendship". I don't think nations would freely trade technology well beyond the ancient era unless they were very close and long time allies, much less sell technology for money. It would also be nice if this would actually let you build up loyalty with another civ. As it is now, civs will randomly start disliking you because you leap ahead in technology even if you do every attitude improving thing you can.
4. Better combat system
It would entertaining to see more strategy in war, or even strategy in the combat itself. The only new dimension in way of combat has been bombardment, which the AI doesn't even really use. There is too little strategy in how to wage war, just when to do it really. :/
Personally, I don't expect civ4 to be "dramatically" better, especially with AI and combat. Look at AI/combat in civ2 vs civ3. Diplomacy will probably be better, and we'll have more of those 'little things' that make civ4 cooler in general (i.e., like luxuries, UU's and civ specific abilities were for civ3.)