It was difficult to find it. Dreamhost was great because I can create a lot of e-mail accounts for my company but in the last year there were a lot of outage that complicated my business. On the other spectrum Google/Yahoo/Rackspace could be great but they are expensive when there is a linear relationship between e-mail accounts and price, and we create new e-mail accounts all the time not only for employees but for testing specific pieces of software.
Leaving Gmail might be uncomfortable, but as long as I can backup my e-mail via IMAP and can move my address at a moments notice, it'd just be a nuisance.
I don't see the point in avoiding Google for the sake of it. But I do see the point in making sure the the effort involved in switching a dependency away from them is reasonably contained.