We struggled a lot in MM9 with the town sizes. I still think that they were way too huge. Like you said, more open space makes a game feel less alive. I always wanted the towns in MM9 to feel tiny and cramped (just like real midieval towns!)

One thing that Bethesda did in Oblivon I'm told is that they had a random dungeon creator that would randomly create the geometry for all levels (including outdoors). then a designer would go through and tweak the level into shape. It's the same approach many of the HOMM levels were created with. Unfortunately, the game is so huge that creating unique looking dungeons would have been a monumental task.