I would like the idea of more maneuverability in Strat warfare, as a result of a larger map... However, that doesn't really get us much right now, does it? More empty space would be boring.
Geography isn't enough of a predictable factor for strategic movement on the map to matter. Maneuvering in relation to hills, forests, rivers, and the like would be amazing and breath life into field battles once more. Commanders would need to consider terrain, for once.
But right now, movement on the strat map isn't fun, and the random maps are not predictable--it's just something that takes time and only really matters in so far as the distance between important things (players, armies, fiefs) is concerned. It's distance, and major (major) geographic shit like mountains and big ass forests, and they matter little outside of large-scale choke points.
---
Or not. I have no idea how to play fucking Strat. As it is, the only fun parts are battles and collecting gear for one's army; watching it improve in the nerdy, RPG sense of things.