This is the first time I am seriously considering leaving Gmail. Seems like a royal pain in the ass to switch though, since you don't "own" your email handle like you would a domain.
The only reason I use them is their spam filters are excellent. Otherwise I wouldn't.
Switching would be laborious if you're using @gmail, probably a case of looking at each unique domain name you've received an email from, logging in and switching addresses. Could be relatively methodical about it by taking a backup and then working down your inbox and deleting the emails from those recipients until you have nothing left. Could be a day job.
There is an option in gmail to forward your emails to another address if you wanted to do it over time.