It may vary from player to player, but if we have a decent pool of pre-made maps i think the re-playability is there since we have alot of game setup options, abilities and strategies to use. Because realistically the existing maps are largely already the same from one game to the next. how about premake the layouts but have the planet types random? If not, make it premade but have the strategic planets in the middle to contest for.
Another game that has alot of replayability due to the expanded map packs is Vengeance.
https://play.google.com/store/apps/details?id=com.prowlsystems.Android.VengeanceAdFree&hl=enMaps can also be premade into a grid setup. like a chess board (4 player) pentagon (5 player) etc.
Or maps with large "Lobes" hanging off tot he side like a peninsula...