I apologize if I come off as "against" the ZOC idea, I just don't think it addresses any of the problems. To be honest, right now I have no problem building lv4+ cities and having rather massive ZOC
Ahh but that's because you're adding in other fixes that increasing the ZoC automatically fixes. Yes, players "Could" build another city within their ZoC, but why bother if what you want is already yours? The problem is Too Many Cities. The only reason the AI (and players) spams so many cities is to grab up resources on the map. Increasing the ZoC spread fixes that with a minimal amount of effort.
My problems aren't with getting Gildar from my cities or anything like that. It's the very simple fact that there Are Too Many Cities, period. Multiple fixes "could" be used, which is true and in the long run probably what's needed. In the short term, they simply need to stop the AI and players from needing to build so many cities to grab up resources that are four tiles away. The playing, having human intelligence, will wait until the ZoC spreads and then build on the new resource. The AI, not having this intellect, Won't, and will simply build a city and then build another city four tiles away, which looks incredibly bad/stupid.
Increase ZoC, increase minimum distance that cities have to be away from each other, then the AI won't spam cities every couple steps. Problem solved...for now.
Of course a lot of the other ideas from this thread should be incorporated as well, like building maintenance costs and some of the other ideas others have had here. Right now though the Devs have a LOT to do to fix things and we need a fast and easy fix. Devs like implementing Easy Fixes. Seen this first hand.
Next, later on at least, the economy needs to be retooled to start working with "Real" numbers instead of 1 and 2 and small numbers. Let's face it, they used small umbers because they are easy to balance, not because they are fun and interesting and make for complex game-play, which they don't.
The number two best fixes out of this whole thread are simple, which I'll state again:
Increase The Spread of ZoC
Increase the Minimum Distance that cities must be away from each other to something like 10 or 15 tiles.
If a third idea is really needed, then Take Away the ability to build another city within the players ZoC, though that may present problems later, I can't think of any off the top of my head at the moment though I'm sure they're there. Still, the number one reason everyone builds so many cities is to get resources on the map. If these resources are already within the factions ZoC, they'll simply build on the resource and won't build another city. Problem solved 
Note: Maybe it's because I Always play with my custom Empire faction, but I don't ever see or build a palace, just like I don't ever see or use the Teleport spell. Maybe the Kingdom factions have these, but as a Empire player I don't, so they've been non-issues for me.
Edit: Kalin: I think the reason you're against the ZoC thing is because of your play-style you show in your post here. You like to Spam out cities so you can build more research structures. The problem with that is it makes the maps look like sh!t. Maybe you enjoy that, but most of us don't. Your main issue seems to be you need more research structure or should be looking to add more research points to get the tech you want. Adding more cities isn't the answer to this. Adding more research structures or re-balancing how much research income you get from those structures is the answer you're looking for and why you seem to be "against" the ZoC increase. Simple fact is, everyone (Ai included) builds more cities to get resources off the map, which someone else stated earlier in the thread.