I just happened across something nifty: you can use the VerifyHostKeyDNS option in your SSH configuration to fetch the host’s public key fingerprint over DNSSEC-secured DNS (with a “SSHFP” record type).
This is defined in RFC 4255, Using DNS to Securely Publish Secure Shell (SSH) Key Fingerprints if you’re looking for some light reading.