If you're setting up a new server, you either have physical access and can use a keyboard and monitor to look it up, or it's hosted by people you are paying to do such things as tell you the key fingerprint.
Hopefully Linode doesn't have any internal gremlins.
Of course, the weak point there is SSL where the keys themselves are transmitted, but it did well to quell my paranoia.