Facebook recently announced that users can upload and publish their PGP public key on their profiles. This seems like a great way to assure you that you are getting a genuine key, assuming that the key owner's Facebook profile is intact.
I created my first PGP key a long time ago, hoping that I'd be exchanging encrypted (or at least signed) emails all the time. But it takes two to communicate. I have already published my public key on my profile. So if we are friends on Facebook, you can try downloading the key and send my an encrypted message.