I checked while playing earlier, and yeah, you can issue orders while paused, though the lines and all which show movement paths for those orders won't appear until you unpause.
I just started a 10-star, 400-planet map, on slow speed, vs 9 AIs in a FFA, with almost every colonizable planet in the galaxy already with a neutral colongy on it, and found that my home planet had two planets, one on each side a short phase jump away uncolonized, and one was a dead end, and the other was an incredibly long jump to the next planet. I'm talking 40-minute phase jump one way, here. It's making for a great game so far, and it's going to make scouting and careful commitment of forces important, because once those forces are committed, there's no bringing in fast reinforcements. I'm probably looking at a several hundred hour game at least, and I'm looking forward to it.
I tried a 20-star, 800-planet map, but that proved to be too much for my computer to handle, and the game was too laggy to play. Ah well. I suppose it might take a lot to keep track of the defensive forces totaling probably around 3200 NPC ships, 2400 NPC space defense structures, plus the efforts of 9 AI factions, but I'm really looking forward to it when I upgrade enough that it can do it.