This is a pretty radical suggestion so I won't be surprised if everyone shoots it down (and then begins stomping on it).
What if a level 1 city occupied one large tile (2 x 2) and all construction happened within the city, in a city layout window. In order to reach level 2, the player would be prompted to build an "expansion" on the actual map to expand the original city. If there was no room the city would not be able to gain new construction spots.
Ideas? Suggestions?
