Welcome to the ex-Googlers 🙂 I too had that realisation that I was trusting every single one of my precious eggs to someone else’s one rickety basket.

Fastmail is an excellent replacement for Gmail and is better in many respects.

As others have said DDG is generally ok, though I have to admit I do have to go back to Google search occasionally for dev queries.

I also switched to Windows Mobile, which is fine if you’re happy to put up with some buggy/missing apps.

http://blog.jamiek.it/2013/08/giving-up-google.html