A simple suggestion. Some grand overtures have been made towards adding "primitive" or nomadic civilizations which would wander the world map and be cityless. However, this could require a large re-working of entities; instead, I offer this suggestion, new "city types".
The "Nomad" city-type would, rather than establish large cities, have the civ create small "shrines" that act as stand-in cities for the purposes of influence area and the civilization's survival. Shrines could include burial grounds, worshipping places (petroglyphs?), or just water sources/other terrain features. (Imagine a wandering tribal society of magma-drinkers.) The civ would then have its collective population move in one large mass across the worldmap, much as migrants and eventually armies are intended to do. They would stay there for a brief time, then depart for the next one, continuing their circuit.
This provides some interest for Adventure mode (encountering a tribe of wandering _____) and for Fortress mode (a tribe of wandering _____ passes through much like a trade caravan, but may attack/declare war on you, especially if you are inhabiting a shrine)
Secondly, the Conquerer city type. It would function much like the Nomad city type, with notable differences; rather than constructing shrines, they would simply make a beeline for the nearest civilized settlement and try to conquer it. If they failed, they would leave and repopulate until they could attack a different settlement. Once they conquered one, they would increase their numbers and attack the next nearest city, and so on and so forth. When they hit their population cap, however, they simply abandon their earliest/farthest-from-civilization settlements and bring the new numbers to the frontlines. Conquerers with a massive population cap could be world-threatening terrors, while those with a lower cap could be barbaric nuisances like _____men.
This would be the perfect way to add threats like marauding armies of Orcs, clockwork legions, Lovecraftian horrors or the living dead, and would be a great way to provide Enemy Fodder for civilized races to ally against during worldgen, and for adventurers to fight when the dragon/ogre supply runs short.
Thoughts?