Kind of an obvious feature to suggest, but surprisingly I'm not seeing other threads about it so might as well make one: Considering Megaglest maps use simple heightmap terrain and real unit positions are always 2D. Would it be difficult to allow automatically generated maps, computed by the engine before the game starts?
When setting up a match, the user would have two options: Select one of the existing maps like you do currently, or have the engine generate a map for you. When choosing the second option, you may optionally edit a few extra fields such as: The X and Y size of the map, how extreme the terrain should be (smooth plains vs. rough mountains), the frequency of trees and other resources, decoration density, etc.
I imagine this should be easy to achieve using perlin noise: Use a random seed for the terrain and for each resource, then scale its brightness to determine height / frequency and its contrast to determine concentration. Then place each player's starting point in the areas which are most open and closest to all resources, and there you have it! This would be fun for people who are bored of the existing maps, and just want something new each time they click the start button.