Okay, you bring very good points, especially on the “changing instance” one. I think I was seeing things from an ideal point of view, where instances just work and there are no reasons to defederate from other instances (but even though I’ve not been on the Fediverse for long, I’ve already seen I think two “big” such cases :( ).
I would say that choosing it for them is not the way, and assigning it randomly isn’t either as there are definitely problems associated with that as well. The best thing that comes to mind is to maybe have some “special” instance (or just an application, kinda like what Mastodon’s Android app does - at least with the new update) whose purpose is to guide users through sign up and choosing an instance. I think this would kill two birds with one stone. Guiding users through instance-selection, maybe briefly explaining what an instance is and eventually pointing to more user-friendly docs, could already be much more manageable for everybody, and could feel like a more seamless experience, similarly to traditional social media.
At the end of the day I feel even more like the Fediverse is almost inherently harder than centralized services, maybe it will take time before people settle with the idea of using something like this. People eventually got how to use the now traditional kind of technology, but I don’t know if it’s because enough time has passed or because it became a necessity (socially speaking).