1) Make it so that your spies in rival territory that you have open borders with don't get caught, unless they attempt and fail to run an active mission. It always struck me as a bit odd that you lose a unit and get a negative diplo modifier for doing absolutely nothing wrong.
2) Exaggerate the rock, paper, scissors element of combat, so that a combined arms force is important, and stacking or not is a real consideration. As it stands, spamming a certain unit depending on era is all that matters. I want siege that does huge collateral to units in a single tile, Changes to, and removal of, some units to give a better sense of balance. I'd also like to see a system where cavalry can choose which unit in a stack to attack, so that they are an important choice for countering siege. This could be balanced by forcing cavalry to fight fortified defenders first. It would require you to control the land adjacent to cities in order to safely move siege into place, rather then the steamrolling stacks we have now, and it gives an outnumbered defender a chance to defeat a larger force through clever play.
3) Remove financial as a trait.
4) Make buildings a viable option. Obviously there are a lot of changes required for this, a lot of which have already been mentioned, and each individual building would need separate balancing.
5) Make unit upgrading cheaper, and unit maintenance more expensive, to encourage a standing army, rather than seeing cities defended by cavemen in later eras.
6) Show more information that was hidden in the regular game. I know BUG solves some of this, but it would be great to see city maintenance rates, what mood rivals won't declare war at, and other very important elements in game, instead of having to check reference charts.
7) Tone down slavery, which is probably the single biggest game breaking mechanic. This would have to be coupled with better AI and removal of AI bonuses, or better yields from tile improvements in order to make higher difficulties still viable. It would be easy enough to tone down slavery, just reduce the number of hammers received per pop sacrificed.