I took the plunge and switched to Fastmail recently. They've done amazing work to make that as quick and easy as possible - in about an hour, they'd imported all my mail, and I had all of my email clients set up again.
I'm mostly off Google services now, but I haven't found a good replacement for Google Maps. I've had Apple lead me into the woods one too many times to really be willing to trust it.