Age of Empires was the other bit of a model that I've had, and in games like that it's pretty easy to plop down a new TC presuming you have the resources for it. There aren't many restrictions on where you can even build the TCs, at least not terribly much. The only real downsides of putting up a new TC is the cost of doing so, and the need to then defend it. In that regard, I don't think that being able to plop down a new TC in this game is extreme at all. It just depends on what game you are comparing it to.
And getting that new town functional right now costs a lot of turns anyhow. 2-3 land bridge tiles, possibly, plus the TC itself. So at least 3 AP. Then all the finished goods producers and a military producer or more. Resource producers if you don't want to be over-extending yourself. Specialty buildings if you want to have units that have upgrades and higher levels and so on. Expense after expense, plus definitely multiple turns of work in order to get them there so that you have a new town that is more than just a single building.
That doesn't seem extremely quick to me; it seems about right. I'm less and less inclined to use AP or even resources to limit town expansion. I'd be inclined to use a different flavor of opportunity cost, of some kind.
---
The idea of making the tiles around towns provide bonuses is interesting, but I'm not really sure how feasible it would be. A lot of different types of such tiles would have to be thought up in order to prevent it from becoming same-y, I think.
---
Another approach would be to time-limit when towns could be built. Either by a simple cooldown (which is frustrating because then you have to time your placements exactly in order to maximize your available towns), or by having TCs cost culture to place. That way you can place towns whenever you want, but you'd need some sort of culture-production method (time plus buildings or hamlets or whatever) to do that. It would be a pretty big rebalance, though, and I can't think of a good model for that that still doesn't encourage lots of towns in the end (more towns equals more culture).
---
An idea that did occur to me was to use bandits as a force against towns. Aka, putting a new TC out also causes a new bandit keep to appear near it. So that whole "you have to be prepared to defend it" thing from Age of Empires suddenly becomes relevant in a really major way. This would be super difficult for new players, though. And in general, really. Unless it was only on harder difficulties, but the harder difficulties are already more balanced toward being interesting anyhow, so that would defeat the purpose.
The other idea was having just individual bandits spawn, which is easier to defend against. But these could spawn in existing towns of that faction, based on how many slots in that town were NOT filled with a ruin or a building. In other words, if you're building new towns without finishing your existing ones, then bandits come out in direct proportion to how unfinished your existing towns are. We could also even make the TC placement interface make this mechanic fairly clear, thanks to just having the tooltip show "X bandits will spawn in your existing towns because that many plots of land in your existing towns have been left empty" or something more thematic. It's not the most graceful, but it's somewhat interesting and probably effective.
---
In the end, though, all of these things except what madcow suggested are coming back to the stick. We're punishing people for building more towns, which I think is not the right avenue for thinking. Why do we care if people do that? It's not an easy strategy; it's fun and balanced and it is the game. Changing that is no trivial thing, and punishing people for playing the game the natural way seems like a really bad move in the end.
On the other hand, what about multiple playstyles? Keeping things small has virtue as well, right? It can also be fun, but it's not rewarded in any way right now. I think that -- the carrot there -- is what is missing. For instance, in AI War it is possible for players to take almost no planets, making things very difficult in some ways, but at the same time keeping AIP very low. It's an extreme playstyle and not what most people do, but it is very useful at high difficulties and fun and challenging even on lower ones. It adds flexibility without ever affecting the way the game was normally designed to be played.
And fundamentally that is what it comes down to: this is a game about expansion and territory-taking. Changing that is making a whole other game, in most senses. That's not a good thing to do to our new audience who seems to like the game and generally understand it. It's not in the service of balance, in my opinion, unlike the changes I'm working on for tonight. It doesn't prevent any cheese strategies or anything like that. However, expanding the focus of the game to present new viable options... of course, that's always great to do, if we can figure it out.
Anyway, those are my thoughts for now.