Search was easy to replace. Bing and DuckDuckGo are both good. Firefox was an easy switch now that Chrome seems to be much more of a resource hog (and the extensions are better). I don't have an Android phone. For e-mail I've switched to Fastmail but Outlook is also a good alternative if you want something free. I don't use anything else. I'd say e-mail was the hardest friction point of them all, but overall it was pretty easy to leave Google.
Despite the fact that I'm not the kind of person who "hates" Microsoft, you've got a point there: they were implicated in the NSA docs as much as Google was. In fact it sounded like they cooperated more than Google. Stick to smaller independent companies that have a good privacy track record.
If you care about e-mail privacy, you should consider desktop/native e-mail clients instead of webmail and IMAP.
Having all your mail sitting on someone else's server means it can be handed over by that company in response to a government request, legal or otherwise. After 6 months, it's not even a fourth amendment issue and no warrant is required; it's not "your" mail when it's data on someone else's server.
This doesn't require technical prowess the average person doesn't have. You can use your ISP's mail server, or a professional service like Rackspace Mail. There are free native e-mail clients for every desktop and mobile platform. You can still get instant mail notifications with IMAP Push. Just set at least one of your computers to delete mail from the server after downloading it.
