How do we start a multiplayer game?

So I'm now programming the multiplayer server part of the game, and I've (mostly) gotten through the name/account authentication part to where I now have to decide how new players will start when they join a server.  At first glance, this seemed very straightforward, but as soon as I started thinking about it more deeply, I fell headfirst into this endless rabbit hole of how Spacemind should be experienced for the first time.

Where a player starts in the Spacemind universe will dictate the initial experience/impression they have, and I know from StarQuest Online that even if you have an entire universe waiting for the player, they'll still uninstall within a few minutes if their starting spot doesn't make sense (i.e. stuck on a random planet with no goals and no understanding of anything).

If I just plunk a newly connected player on a random planet, then they're probably going to feel lost and frustrated very quickly, especially since the space aspect of the game won't become apparent to them until much, much later.  (Outside of the very small ones, spaceships are going to take serious resources to create)

On the flip side, if you start everyone on the server character's ship, then the difficulty of finding/boarding/building a ship is lost, and if the server is public, then you might not want random people suddenly appearing on your ship to grief it.

For single player, I have a good story-based initial experience that will give you a taste of a real spaceship, a broken spaceship, your place in the story, and an initial planet to explore before you can continue on your journey.  For multiplayer, that doesn't make as much sense to produce that for each connected client.

I just need to think long and hard through this problem of how new multiplayer players should begin their journey on someone else's server before I write even a single line of code about it.  I don't feel like I've wrapped my head around the ideal answer to this problem yet, and I'm worried that this decision will have an enormous impact on Spacemind itself.

Time to go think in the dark.  I'll let you know when I've come up with something.