So I know that on Gigantic settings that the map size is 18x18 parsecs. That's pretty huge, but what if you want a bigger map?
Why not allow a larger size map by building in to the game a new game play element:
Exploring the unknown regions of space beyond the maps edge.
Once you've worked up the Ship Sensors tech line you could get a new tech, perhaps called Deep Space Exploration. This opens up new modules for ships or starbases that allow you to "scan" off the edge of the map for several turns and open a new parsec of space. Could there be new planets (5% chance)? Anomalies (10% chance)? Resources (5% chance)? Most likely nothing at all (75% chance)? Or something totally different and unexpected, maybe even terribly dangerous (5% chance)?
It'd be a nice idea to satisfy that exploration aspect of the game in a whole new way. You could just keep opening up new parsecs until you got tired of it. You'd also get some different shaped galaxies too, sprawling in all sorts of directions instead of one big square block.