TL;DR: Using words instead of strings / images may be a good solution for short, easy-to-verify codes and using locality / time dependent verification codes strengthens short hashes as would using password-hashes.
Additionally to the improvements to comparability of the hash proposed by A. Toumantsev, I will propose three extra measures which I believe may be more unconventional than his solution but will adapt to your situation in a better way.
The challenge you're facing
You need to reduce the output size so much that a user won't get tired comparing two outputs, making the comparison short and / or interesting is the obvious solution.
At the same time you need to ensure that the output is not too short, or an attacker will be able to brute-force keys with the same output and thus will be able to fool the user and accept a man-in-the-middle attack.
Improvement 1: Don't use images or QR-codes, use words!
Images tend to be difficult to compare properly and chances are that the user screws up the comparing process as much he can do with long number strings, in fact if the image is high-resolution it may actually prove more difficult to do a proper comparison.
Randomly selecting a word in the user's native language for each byte (or maybe two bytes) and showing the user a "sentence" consisting of 16-32 such words may actually be feasible for full comparison. This would then benefit from the Stapled Horse batteries effect and be easier to remember / check, much like passphrases are easier to remember than passwords.
Of course this only a suggestion and actual tests are required in order to find the most effective solution.
Improvement 2: Buy yourself strength by imposing time limitations
You are in the lucky situation that the parties wanting to verify each other's public key can communicate. This way you can randomize the verification process, because if an attacker found a key that passes your 64-bit test, he will probably fail your randomized test, so just let both devices exchange a random nonce and display the properly encoded $\operatorname{HMAC-SHA256}_{\text{Nonce}}(\text{PublicKey})$ for verification to the user. If you let this HMAC expire after an hour or so, you effectively only give an attacker that time amount for finding an appropriate second-preimage.
This trick with a 128-bit nonce would allow you to reduce the shown value's size to somewhere around 64-128 bit (less would slowly become dangerous again) while still maintaining strong security.
You may also want to give the user an option to mark a certificate / key as "verified" for this method.
Improvement 3: Password hashes
You can combine the above three methods with a password-hash that takes a few hundred milliseconds on your devices (using the nonce as the salt and the key as the password). This way an attacker has to spend a considerable amount of effort for each key generation, slowing down any brute-force attack attempts. With this method you can probably gain 10-20 "bits" of security without any problems, allowing you to shorten the displayed value even more.
