Even though I have not played Civ IV yet (I have read a lot though, am waiting on a new video card to play right now), It has been stated in ways several times. All those civilizations, leaders, buildings, wonders, and units that were in Civ III should be in Civ IV. I hope the next expansion would revive all those.
Upon thinking what original things could be added in, I remember comments on wanting to add on privateers to the game. If you want to add privateers, why not expand on that with taking barbarians one more step and creating a pirate entity at sea that no one controls? The pirates could pillage improvements made on water, and cause unrest at ports they are nearby.
Another idea that I read previously, the Civil War idea. It is a interesting idea. Instead of having the cultural conversion, could a totaly new country be formed from part of a existing one? It would be hard to implement. I remember that this was something pushed for in Civ III. I think one thing to consider is how to make such a system work?
Also, I thought about taking a more recent page of history, the anarchist and terrorist? Could they be put into the game somehow? From another page of history, special interest groups have shaped history significantly. Be they the rich, the farmer, the middle class, a minority, or whatever examples one can think of, but how could influences of special interests group become a part of the game?