With the introduction of Immense sized maps, the beginning of any game is going to be fairly slow. Ships take extreme lengths of time to travel between planets, and--well, immense amounts of time to travel between races. However, on Tiny maps, you run into each other almost instantly.
I propose (perhaps a gameplay option?) that we have scaling default movement speeds.
So for example, the Medium map would have the current default shipspeed. The Small would be -1, the Tiny would be -2. The large would be +1, the Huge would be +2, Huge might need + 4, and Immense really ought to start at +5 or 6, or maybe even 7.