Comment by nine_k

For physical devices, you can usually connect them via a dedicated Ethernet cable right to your laptop, and set the initial password. They likely don't have the right network settings anyway to drop them right into the bigger LAN.

Otherwise I think you just prepare a certificate ahead of time, and scp it during the first connection, then immediately disable password-based access, or at least change the password. Any passive eavesdropping still needs to defeat the encryption somehow (no feasible ways are known now), even having seen the initial exchange.

If you have an active MITM attack, all bets are off, because the attacker could even grab the image with the pre-baked key you're sending, and copy or change the key. If this is not possible, then the pre-baked key would help. If your security is really important, don't use ther cheap GoDaddy's offerings with limited SSH.