Procedural Generation?

I'm not really sure how you are weighing procedural/predetermined map issues here. You say that you're interested in procedural generation as new players come in, so to me that sounds like you're thinking of expanding the map to accomodate new players. If this is the case, what's your alternative? To keep track of how many players are joining, and then create new map segments on your own as needed to handle them.

If this is something that you think you might need to do often, it would probably save you time to write some good code to generate areas on demand, and so save yourself that work each time it would come up.

If, on the other hand, you're looking at generating an area each time a player goes there, that's a different story. That would be a bold design choice, because it forces luck to be a play mechanic since there's no way to bookmark an area and return to it for any reason. So some players will stumble across goodies fairly often, and others will be space-dirt farmers no matter what they do. That sounds irritating to me.

There are other possibilities of course, but those are the ones that leap out at me first. Ultimately what direction you decide to go will depend on aspects specific to your game, and we don't have enough information to get into much detail on that.

The answer to that question depends a lot on the scale and detail of your 2d universe, and the gameplay requirements.

Memory considerations:
-If you are creating a galaxy which contains a small amount of data which can be kept in memory at all times, then I suggest creating the whole galaxy at game start and keeping it available throughout the game.
-If the galaxy is big, the procedural generation could take a longer time and consume more memory. In that case you may want to create sections, and establish some sort of paging mechanism so that sections load from disk (threaded) as the player moves along. This would keep a reasonable amount of data in memory.

Loading times:
-In both cases you are probably better off to generate the galaxy before the players begin playing. If it's an immensly huge galaxy, and you cannot store the data on disk, or the likelyhood of using all the data in a single game is small, then you should generate the sections of the galaxy as players move closer to them. However, this also depends on if the generation speed (depending on complexity and inter-connectivity, etc) can be good enough to not cause hiccups during gameplay.

So you see, there are a lot of "if"s to your question, and a lot depends on: how big and complex the universe is, how fast the players move through it, how quickly you can generate the galaxy at desired level of detail, and the ratio of movement speed vs generation speed (if low enough, can be real-time procedural).