If you buy a VPS, you need to trust the company hosting it.

I would NEVER trust anyone other than me to handle my privacy and neither should you, you should always use PGP to encrypt private emails and do the encryption on your PC (not using your providers server-side tools).

The email provider I use is https://unseen.is
They are based out of and hosted in Iceland and are OK although they lack the functionality of using "+" aliases in email addresses. I PGP encrypt anything sensitive so I do not need to trust them - the main driving factor behind choosing them was the cool domain...