If clicking a prominently placed button to lookup a key is not intuitive, then how do these users manage the just as unintuitive process of finding, verifying, and installing an application on their device?

Keys are searchable over HTTP/HTTPS, and the HTTP derived (insecure) hkp and TLS-secured hkps protocols. The whole point of PGP is that you don't trust the source of the key without verification, so the protocol over which you receive the key doesn't matter.

There exist a plethora of implementations that hide the trust-building exercise from users, and they're all for instant messaging. You can shoe horn that into email, but why? PGP is based on the web-of-trust principle of verification; if you just want the attestation that UserX probably owns KeyX, use a service that's tied to your phone number or email that doesn't use PGP -- i.e. textsure, telegram, whatsapp, etc.