Multi-layer maps would be cool. In my opinion even necessary. I like the city building part, but i hate that after some time whole continents are clustered with huge cities. so large that a mounted army would need two seasons to get from one end to another.

with a Citymap where you can build your city as now, but just require one tile at the beginning. so till lvl 2 a city will use 1 tile (the small one), then lvl 3 and 4 will use a whole square and a lvl 5 city will use 4 squares (2x2). The cities would better fit into the scale and not just consume the whole space. special buildings like Fortresses can have an extra tile so you can see them from far.

Battle will carried out on a part of the city builded and not just on random map.