Production boxes are not allowed to be plugged into bare internet or DMZ unless they were seasoned and tested on the LAN first, and the LAN allows no external traffic in (stateful firewall). If people on your own LAN are trying to pown you, you got bigger problems to solve before installing another box.

In the old days this was manually moving ethernet cables, now a days this is changing which VLAN the virtual image talks to or if you use something like openstack that implements its own firewall at the virtualization level you allow no external traffic in until the config and testing is done.

Also you need to verify your install media is not powned, which means you need access to the md5sum of the media (and how do you know someone didn't MITM the correct md5sum?) and you need to verify your md5sum program isn't powned which means you need to verify your verification strategy isn't powned which means this gets recursive real quick.

In general a VPS should come up more or less up to date with your SSH key pre installed and no services running except SSH. It may permit password auth but no accounts would have passwords.

I was going to ask the same thing. How do you stop someone from owning a new Linode between the time you start the server and the time you disable password authentication?

I build images locally in virtualbox/vmware player/kqemu/whatever and upload or copy the image over after they are configured minimally.