The galaxy generator should have another type of variance -- eccentricity. At low levels, it should strongly fit the galaxy shape (and largely generate galaxies the way the generator works now). At mid levels, it should be willing to sprinkle systems in empty places (including, in larger maps, voids between galaxy arms that you'd only be able to explore if you send your ships flying through these voids. At high levels, the chosen shape would still be recognisable, but other regional shape motifs would be strongly present.