So there are three different scenarios wrapped up in this question and they're all interesting.

A. The server is new, and I'm setting it up presumably remotely e.g. in "the cloud". Ideally the autonomous setup should provision keys for me in this case, since they're public it's fine to even publish scripts which do this. However it's true that there are a lot of systems out there which instead give you a password for first login (or worse they have a fixed default!) which is sad.

B. The server has existing users, but not me. If we're not using certificates then I need an existing user to authorise me to use the machine, providing public keys is no different than anything else they might fill out, like my name, they will need a trustworthy source for all of it. For systems I have no other prior relationship to beyond that I am, as you see, tialaramex, I tell them to add the github keys for tialaramex, which are of course published. I will replace those after successfully connecting to their SSH server.

C. I've used this server but not from this machine. FIDO resident keys solve this (you can extract the resident key to a new client from your physical device, the device still needs to be present to actually authenticate) but I will also use SSH to connect to my home bastion and have that authenticate while I do setup once. I can SSH from my phone, so if this can't work then somehow I don't have my phone or access to my home, setting up SSH keys is a low priority in that case.

However it's true that none of this is yet ordinary.

When you install Ubuntu it asks you for your Github username and pulls your public key from there, making having the corresponding private key the only way to log into the system.

If you lose all your key material, then I wouldn't expect for you to ever be able to log into the system. Passwords have the same problem; if there's some machine you can only remotely connect to and you forget your password, you simply won't be accessing that computer anymore.

Keep following your own logic. If you don't have a preexisting key relationship and you can't trust the network, are passwords safe? [Y/N]

Depends on how the server was setup. Ubuntu has offered importing public keys from github for quite a while in its installer. If you're using terraform/ansible/some other IaC tool, adding a key is probably just 1-2 lines of code. Some OS, like Guix or NixOS, also allow you to define them in a config file. Worst case you can just do something like `curl -L github.com/username.keys >> .ssh/authorized_keys`.

What's the use case for using your personal unix account on someone else's computer?

Of all the use cases I can imagine, enabling password logins just so I can meaningfully type my password into strange computers is among the least compelling.