First, somehow make popular email software developers (Thunderbird, Mail.app, etc.) to include OpenPGP support out-of-the box and make it easy to use. I.e. not

First, somehow make popular email software developers (Thunderbird, Mail.app, etc.) to include OpenPGP support out-of-the box and make it easy to use. I.e. not a scary-looking interface hidden beneath 4+ clicks deep in settings, but a simple-to-get "security" button and an unobtrusive suggestion to generate or import a keypair on account creation. This is an absolute necessity. For webmail providers ask them to at least provide signature verifications for PGP-signed mail - that should be acceptable even for Gmail-like ad-based mail-sniffing business model. Then, just start using OpenPGP. For every recepient with a known key encrypt the message, for others - sign it. Users will notice your emails have some fancy security-related icons and curiosity will eventually prevail. Almost works with S/MIME for me (but since obtaining a certificate is not trivial - only "almost", not really).