Perhaps a random map generator ... but taking into account of surrounding terrain. If in between mountains, have sloping hills throughout, especially rising towards the edge, growing into unreachable areas eventually.
if surrounded by a forest, lightly forested glades interspersed throughout the map with thick growth of forest nearer to the edge.
Near a lake or ocean ... and part of the map (up to a third, no less than a tenth) will be unreachable by (most) units ... proposing a possible tactical advantage to flying and swimming type units.
In fertile land or floodplain (high chance) and most other terrain (low chance) for a river to run through the map (various sizes) although biggest rivers be found in River Deltas/Swamps and the non-Delta river-mouths ... both are near the coast ... so essentially the closer to the coast the larger the river could be (on average).
Most rivers could be waded through at several points, some rivers shallow enough to be only a minor hindrance ... and others would perhaps need an on-map bridge structure in order to be crossed. Spells, work-crews, and help from aquatic life could help in crossing a particularly troublesome river ... although taking and holding bridges could be a strategic advantage ... and destroying a bridge to deny you enemy that potential would be an interesting decision. I propose that if well within your territory building/rebuilding a bridge should take little effort, although the farther away from your capital, and the more enemy units in the area, the more difficult/ more expensive recreating a bridge, or magically making the river section able to cross (temporarily) will become.
river, ocean, and forest could be interesting terrain where certain types of training and equipment could provide bonuses and penalties.
On the same token, snows/ ice and desert sands should have similar effects. For the most part heavy snows and desert heat would increase exhaustion, while desert sands and permafrost would restrict movement ... and possibly incur a penalty in either defense or attack.
an effective strategy certain desert peoples used (against the romans I believed?) was to ambush them by pouring tar (hot tar?) onto the soldiers, and it gets inbetween the metal armor and makes them scream in agony as the real threat clamors down (or reveals themselves) and commits to the slaughter.
In the other extreme, specialized barbaric forces in the north would use a combination of winter snows and woods to hold effective ambushes ... however ultimately the winter was a drag on both forces ... those accustomed could use the natural advantage to great affect in specialized circumstances. Other than an over-all light bonus to the conditions. (but commando units specialized to the terrain usually suffer without their terrain bonuses ... desert ones for instance, due to lack of armor)
