If you are connecting to a new host for the first time, what is to stop an intruder from performing a MITM attack: swap out the public key and fingerprint for a public key they have the private key to and the fingerprint of that new Pub-key? Thus getting all the information, so the user never actually connects to the correct server,since there is no form of PKI with certs. Is this mitigated somehow?
If you connect to a totally unknown server, you can indeed be victim of a MITM where someone gives you the fingerprint of a key-pair he controls.
However, the way to go is: setting up the server, get the public key's fingerprint. Then you can validate the fingerprint you see on connect matches the fingerprint you know from the server. If someone were to perform a MITM your client would show a different fingerprint.