Recently (really?) I got following idea:
to have files (loadable from new game dialogue) where could be written coordinates for cities as they shall be prepared into map.
for example
Sázava: 300,500
Jihlava: 400,1000
In this way, one map would have many stable (design of cities would be still very random) citylists. I cannot say how much faster would be creation of new map in this - but it could be neutral to paksets.