It doesn't matter if public keys are exchanged through an insecure medium as long as there is a way to verify them. Someone else seeing the key is not a problem, so Google being able to find them after the fact would be fine. The problem comes from being able to MITM them and swap it out with a fake key controlled by the attacker. Verifying the key fingerprint (using GPG terminology here, don't know how it applies elsewhere) after via another means (ideally voice or video) would confirm it's a legitimate key.
Generating an easy-to-recognize image from the key fingerprint would be a lot more approachable to the casual user than trying to verify a long hexadecimal number.
I guess you're then trusting whatever 3rd party handles the image generation.... but at some point you have to trust software that you didn't write yourself.
