Instead, we need to reward players more for building up fewer, bigger cities.
Brad already has the right idea here; there's no need to punish players for spamming cities. You just need to give players a better option instead of building new cities, such as improving existing ones.
Say I have a level 5 capital, two level 3 cities, and 500 gold to spend. I can spend that gold on a new building for my capital, or spend it getting the 3's to a higher level, or found a new level 1 city. To cut down on city spam, you just need to make the first two options more effective than the third.
So what if, for example, there were a bunch of uber buildings only available in level 5+ cities, each of which costs 500g and produces oh, say +20 of some resource, more than you'd get out of an entire level 1 city. As long as my capital has room left, I'll be saving my gold for those buildings rather than spamming new cities. And when my capital is full, I'll be spending my gold on the level 3 cities, getting them up to 5 so they too can have their uber buildings. Sure you could spend that gold on a bunch of level 1 cities, but it just wouldn't be the best option for improving your empire, players (and well designed AIs) will generally go with the smart choice.
If city spam is happening, then it's probably because it is the smart choice - you don't need artificial limitations to fix this, you just need to rebalance the game such that it's no longer a better idea to build a new level 1 city instead of improving existing level 5's.
Practically speaking, I think the main cause of city spam, right now, is materials* - unless you take the lumbermill trait, the only way to produce materials is a bunch of little workshops any level 1 city can build. Materials and gold are the primary 'economic' resources used to make the buildings that produce more resources, and while level 5 cities can produce several times the gold of level 1s (thus providing an incentive to level up cities rather than spam them), my level 5 capital still produces 1 material per turn just like any level 1 city - this is a problem. So even if I really, really want to develop my capital fully and I really don't want to spam a bunch of little cities, I still have to city spam just to produce the materials to develop my capital with all those essential economic buildings. This isn't a flaw in the game mechanics, it's just a lack of material producing buildings above city level 1, easily fixed by giving everyone lumbermills back and making the trait do something else (a third material boost on top of that, faster build times?).
Now, materials aren't the only problem, just the biggest one at the moment. There are other changes that'd help - increasing the cost of new cities, starting with less gold, adding more buildings only available at higher city levels (like the hypothetical 500g uber building mentioned above), there isn't any one magic change that would fix city spam. But these are all easy changes to make, and such balance fixes are all that's really needed, not new game mechanics like city maintenance costs, paid upgrades, taxes, etc. I'm not saying those are bad ideas, just unnecessary when a few balance fixes to existing game mechanics would accomplish the same thing.
*Edit: I'm deliberately ignoring another major cause of city spam, building level 1 cities just to get some essential resource - because, I hope, this'll be going away anyway with the promised changes to resource gathering.