I have a few ideas, these are more for Civ 5 then adjusting civ 4
First of all Cities.
OK, take here I live as an example. Here in Adelaide Australia there is a fair bit of fertile land in a small area surrounding the city itself. And along the river land about to hours from the city. The state itself to which Adelaide is the capital is vast and arid but there are small towns dotted through it for mining and taking the vast mineral wealth out there. The state is by no means an circle around the capital, it has adjusted to take in the best of whats to offer.
The way civ portrays cities and the area of influence works well for the ancient and medieval eras where transport is an issue, but closer to modern eras it just doesn't sit right. The cities should be reclassified as states not cities. and the fat cross should be abolished. The area of influence in the state should be adjustable.
Think of this. the city/state controls its 3x3 it starts with and begins generating culture (oh god please re-name that). as it accumulates culture the player can go into the city screen and "buy" tiles for that city/state to work, provided it is connected to the rest of the city/states influence. Or you could allow the computer to do that for you.
The second issue I have is towns.
I like them, use them a lot, but there not realistic. Historically towns exist for several reasons. Either they arise at a cross road on a trade route to cash in on passing merchants, or they arise around a particular resource to house the workers and grow from there.
I'd like to take the current option of "Build a cottage" and replace it with;
-"Establish Mining Community" on a tile next to a mine, or several mines, increasing in

value the more mines it controls as well as size.
-"Settle Farming Community" next to a farm/farms providing additional

per farm, maybe also a

bonus.
-Trade Towns should not be built, but appear on there own along trade routes. acting like normal towns do now they could also add to the value of trade routes.
Also depending on how much detail and complication you want to give it. These towns could eventually turn into cities if they are far enough from the capital. This could replace the settler function if done properly.
Some other ideas
- Bring Back Outposts
- Give units the ability to fortify and block terrain. (a mix between civ 4 and 3 there)
- Internal Trade routes need to be revisited. One source of gold does not satisfy a nation, trade routes should be setup, where portions could be allocated. And food trading. Seriously. Food exporting is a huge industry globally.
- More random events
- Listen to what the others have suggested with diplomacy
- New worker function of building solar panels late game in desert tiles.
Lastly, I want my civilization to keep going into the future. You cant expect me to believe that humans reach alpha centauri without moving into space around earth first. Let us establish space colonies, and underwater research stations. The oceans must be full of resources. Cities on platforms on the oceans would be incredible. Ocean Bridges (like 3 tiles) connecting nearby continents. The race for mars? I wouldn't mind a version that demands you survive Armageddon either. So much potential to continue into the future.