I realy don't understand how you can all like this feature as is, imho it's absolutely horrible. It was okay to experiment with this in WoM, but the experiment failed. The whole city building part of the game should have had a major overhaul (like tactical combat for instance), but the changes that have been made seem 95% cosmetic. Without some radical changes this aspect of the game will never be more than mediocre. I'm pretty sure there are more people feeling this way, city management is the second highest scorer in brad's recent poll (even though it was only added afterwards, something that worries me more than slightly).
If it were up to me it would be totally redesigned. But as that is unlikely I'll make some suggestions to salvage it;
1) Building tiles should be restricted, perhaps to only the first ring of tiles around the core. That gives you anywhere from 8 (for large buildings) to 32 (for small buildings) building slots. No more snaking, no more teleporting, no manipulation of influence, more strategic choice of what to include in the city walls.
2) There need to be way less buildings, and each building needs to be more significant. There are about 70+ buildings in the game right now, I would cut that number in half. Or make half of them available to kingdoms and half to empires. Most of them just give +X resources or +Y% production, which is very boring. Make them interesting, for instance by tying them into unit production. So you can't train units with a trait until you have a barracks, or can't train horsemen until there is a stable. (There need to be some interesting option for the more civics or magic minded players to, but I honestly can't think of anything right now.)
3) Make buildings upgradeable (by choice, NOT automatically). This way you can provide more of a certain bonus without the city taking up more space on the map.
4) Give us more to do outside cities. Apart from resource tiles, there is nothing to do, and once you have build on those you never have to touch them again. Make resource tiles upgradeable, so I can choose to have them produce more (at increased costs of course). Make it possible to build more than one type of building on a resource tile. So for instance at a skath pit, I can choose to use them as mounts, or hunt them for sport. At a scenic view, let me choose between building a diplomatic capital generating palace, a (money?) generating private estate, or an unrest reducing public park.
4b) Outposts could be more interesting. Now you build them and you're done. Make them upgradable to cover more ground in your influence, to give defenders a defence bonus, have a militia, or even recruit units from nearby monster lairs.
4c) How about being able to build farms or farming villages on fertile lands around my city? This space just seems wasted right now. This way you could cut a lot of the +X grain or +X food from grain buildings, that are a bit counter-intuitive imo. And it will make the countryside seem more alive, and give you something to raid (or defend) rather than having everything safely behind "city walls". There should be some limits to this obviously, as I wouldn't want a civ-like spamming of improvements. But maybe 1 village per city level? And/or a minimum distance between tiles? Logging camps and fishing villages (on coasts or rivers) are other options. This will also create a difference between relatively safe heartlands where it is safe to build these structures, and more uncivilized area's on your border near enemies, wildlands, or uncleared monster lairs.