Random thoughts:
Pick a good ring-type city, Neverwinter maybe? can't remember, split into 4 quads (or larger, depending on how big the map is and how large you want to slice it). I think ballbarian or someone made a ringworm map (91 provinces)that was a similar idea.
Have the center be either a single province or a small group of provinces with something fun (high resources/income/gems, recruitables (maybe the royal army), a castle - palace. Possibly VP and play cumulative VP.
If possible (and I'm not sure it is) mod out forts or make them prohibitively expensive.
probably mod out teleport spells, or at least the common/easy ones.
Say 2-3 players per "slice" (if 3, the point player will be at a slight disadvantage with more fronts, so reward them somehow).
Have 2 entrances per wall, and a main gate at the point, so 5 points of entry per slice.
Create 5-10 pop types (is this even possible?) for independents. Generic could be thieves, mages warriors, etc or nobles/upper class, lower class/peasants, middle class/tradesment, military/royal guard, underworld/thieves, religion/priests etc.
Create 4-8 "Races/Nations" Gang 1, gang 2, etc relatively similar with 1 or 2 unique abilities/commanders. Pretty much start with an even playing field. Or go nuts and have them be completely unique - "Necromancers have infiltrated the city and try to take it over during the time of strife" or have it be 8 nobles fighting for the crown a la Song of Ice and Fire, 8 vying temples/religions a la dominions
Could also do a sewer like Taqwus mentioned, have a couple provinces per "slice" (or even really, really tiny provinces as sewer entrances) that neighbor to a sideboard cutout. Could either be started empty, with "monsters" or as the starting loc for thieves/necro/underground races.
Be kind of neat to have a 4-8 player map where everyone started out with similar nations. Give them all specific pretenders, or a small list, and drastic restrictions on pretender creation.
Something like the 8 nobles fighting for the crown idea - troops are going to be relatively similar, nobles will be relatively similar, and each might have a unique feature and unique path.
Everyone can build
Units
Knight
Swordsman
Pikeman
Xbow
Longbow
Peasant
Commanders
Scout
Ranged
Melee
Magic
Priest - 2H
mage/priest combo
And either a unique unit or ability for all units. Possibly limit max magic level to 2 to simplify the game.
If that turns out to be boring, can always edit units after.
Like i said, real random