One tip: make it dead easy to set up. Look at the Text Secure app: you can first pair with just a click, and everything is handled automatically through SMS. Nothing to type. The verification part is a bit more involved, but easy to do with QR codes.
The real problem with end to end security and things like email is that you cannot automate it without a central authority. You will still need to exchange keys at one time, and making that secure is hard.
If you are ready to make compromises, you could set up email clients so that they always send their public key in a header somewhere (or a pointer to their public key). You would not be sure on the first exchange that it is really the person you are talking to, but you would get the assurance that future messages come from the same person.
