I actually just began the process of migrating away from Google about two weeks ago. I chose FastMail for my new email provider. It's $5/mo, but honestly, I'm fine paying that, solely to get Google out of my emails.

I find their UI to be simple and clear. I enjoy the notes/calendar features that come with the email. Their mobile app works fine on my android phone, and the push notifications from the Fastmail calendar are relatively unobtrusive.

Only downside so far was I had to cancel my NYTimes sub (honestly probably a plus) because it doesn't recognize the @fastmail.com domain as a valid email address. It's the only service I've had that problem with, including the important ones like banking, etc.