First contact when using Public-key cryptography? Are there any "smart", useful ways when doing first contact in Public-key cryptography? Besides physical contact.

Example: SSH has the "VisualHostKey=yes" (but this also requires to know the image...)

Visual Validation of SSL Certificates in the Mozilla Browser using Hash Images
https://www.cs.cmu.edu/afs/cs/user/mjs/ftp/thesis-program/2004/tay,evelyn.pdf
You're asking for techniques to establish trust in a public key upon first connection. There are three major approaches to this problem:


Out-of-band-verification. This generally relates to methods which use methods which don't go over the current communication channel to verify a public key.


Pinning. If you use pinning, you hard-code your public key (or a hash thereof) somewehere (for example in your app) and then validate that the pin matches the public key. This is also done in browsers, for example Chrome pins the Google certificates. Also there are ways for webservers to signalise that they want their current public key pinned (HPKP).
Physical verification. In this scenario you likely want to confirm the public key associated to some physical entity so you go to that person, verify their identity and then associate the public key they claim to belong to them (in person) with them.
Other channels. In this scenario you generic "other channels" for your verification. For example if you want to exchange PGP keys, you confirm the hash of the key over Twitter or your favorite messaging app.

Certificate Authorities (CAs). This is the approach where one (or a set of) entity(-ies) certifies a public key to belong to a specific entity (eg a person). The signing keys  of the CA(s) are verified out of band (as per 1).


SSL PKI. For the web, the summary basically describes what is done.
DANE. DANE means that you put your public key (or a hash thereof) in the DNS so it can be confirmed "out-of-band" that way. This is placed under "CAs" because the DNS itself is secured by DNSSEC which has a strict CA hierarchie.

Web-of-Trust (WoT). In this scenario everybody becomes a CA basically and certifies other people's key depending on the verification they have reached out-of-band. This allows you to traverse the graph that the WoT forms and find a path from you to the new public key, maybe because two of your friends already have seen and verified said public key.


PGP WoT. The above is basically how the PGP WoT works.
Notary-like Approaches. This is a slightly different approach but is also based on the idea of "many CAs". Basically you have a set of (more or less trusted) notaries and each time you encounter a new website you ask them what public key they see. If these match what you see you have some confidence that your key is good if not, you know you're attacked. 

Trust-On-First-Use. This approach is the most straightforward one. Assume the first connection is ok and keep the public key or a hash for verification against later connections. Obviously this doesn't solve your problem.