Just started playing a few days ago, and am loving it so far. I have no idea how hard it would be to do, but I think it would be awesome to have randomly generated maps where you would need to explore to reveal terrain. (Perhaps combined with units having a sight range, and a spell that reveals some amount of map around you.)
It would be a fairly large change but not completely crazy.
I think it could be fun to go out searching for where the zombies are!