This hinges on this being either a VM or some hardware you've set up yourself.

what other situation would you be in?

Any device where you don't control the initial firmware, and the firmware doesn't support ssh keys. AP/Routers (consumer and commercial and industrial grade), Shared hosting with ssh but limited features (eg GoDaddy)...

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.

Let's say you bought a router and now you want to log into it.

Then you connect physically and do whatever is necessary to prepare that router for your intended use.

Connect to what? It only has an ethetnet jack.

Your laptop, for instance.

Are you being intentionally difficult or have you just never bought and set up a router?