Why not just use Gmail1? Because if you're not paying for the service, you are the service. Google gives you Gmail for free, and in return they analyze and market your data. That's a fair deal, as far as I am concerned. But not a deal I want to make.
For one thing, I just don't like the idea of someone else reading through my email. Furthermore, I'd like my emails to be hosted in the same country I live in2, so that all the laws that protect the privacy of my letters are just as valid for my emails. So a German email provider it is.
First, I tried mail.de. They show ads, even if you pay them. Also, their web interface is surprisingly ugly. No thank you.
Then, I found posteo.de, and they seemed to be doing everything right! Hosted in Germany, a buck a month, with a focus on security and privacy, and seemingly developed by friendly people. They even try to be environmentally friendly. In summary: perfect!
After half a year of using Posteo, though, I have found a few niggles. The web interface can't search mailboxes with a lot of emails–I have an archive directory with 14k emails and the search wouldn't work. Their support says that's because there are too many messages in that directory. Also, they have had a bit too much down time for my taste: I experienced three outages of about two hours each in the last half year. Not a deal breaker, but it doesn't exactly instill confidence in their infrastructure.
Enter mailbox.org. Also German, also a buck a month, also friendly and safe and eco-conscious. But with a much nicer web interface, support for custom domains, and a working search box. They even support ActiveSync, which you'll like if you use Outlook or Windows Phone. In other words, Posteo done right. I'm sold.