I recently attempted such a move, but Google docs held me back. I realize any true paranoia agent would never use Google Docs, but if you ever collaborate on documents it is irreplaceable. Not to mention other people are creating shared documents on Google Docs that I need to use.
True, I could move just migrate the email, contact list, and calendar somewhere else. But then I would have two contact lists that need to be synchronized between my new provider and Google Docs and forward any notifications from Gmail.
Then I realized just how much I rely on Google's email search. Finding an email within tens of thousands is instant on Gmail. It is nearly impossible with anyone else.
In the end, I abandoned trying to move away from Gmail / Google Apps. After all, there is nothing stopping the admin of any email system from casually reading inboxes or being forced to turn over data to a government authority. And Google does have some history of fighting back for information requests, where I can see much smaller providers folding under pressure more quickly due to limited resources.
And the argument against self hosting has been repeated here already, but the risk of loss of service is far, far the worst thing to happen for email. If you don't care if your email becomes undeliverable for hours or days at a time, you really don't need to be paranoid about email.