Using a different operating system than Android may not improve your privacy position. Microsoft and to a lesser extent, Facebook, have attempted to compete with Google's product lines. Microsoft has operating systems and phones. Facebook has social networking and to an extent, search and voice (in partnership with Microsoft). So you'll need to decide if the replacement, as a cure, isn’t worse than the Google “problem". In some cases they are -- and it's a matter of trust to use these products, even if you agree to the terms of their licensing.
Why bother to read the agreements? They're legally binding. Vendors of the products you use, subject to the licensing agreements that you agree to, can use the information in ways you didn't intend. This means both with your desires, but also against them for the desires of others. Can an insurance company deny you a policy because you've been searching extensively on diabetes and cancer? Perhaps performing a query on low cost legal services, or learning about HIV might peg you as an undesirable. Findings might be quotient of a decision process that you have no control over. It might be best to move on.
Where ever you go with a mobile phone that's turned on, that phone broadcasts its location, and that location is tracked. If you use the GPS functionality of a mobile phone, then you're now in a very precise location-based tracking system. The GPS chip will rat out your location. This was originally a function to help telcos serve your phone with the best tower location. Now it can be used for whatever purposes the telco wants.
In the US, telcos will give up a history of your calls and location (of your phone) to law enforcement officials. Burglary some place? Were you nearby? You're a potential suspect. Calling people with conviction records? Oh dear.
Talking to someone with a conviction near the scene of a crime? Oh my. The telcos have a history of releasing location-based system (LBS) information with hardly a warrant. Governments can keep track of your location, and in some places, listen in on your calls, you terrorist, you. How long do they keep the data? I sense that data is forever.
Day six: The replacements
Here's a list of possible application replacements for things Google might be currently doing for you:
Google Search: Duck Duck Go, doesn't store info or cookies; no location-based tracking
Google Plus +: Social Networking Portal, numerous alternatives
Google Docs: Numerous alternatives
Google Mail: Numerous alternatives
Google Translate: See alternativeTo for other choices
Android: Boot-to-Gecko, Ubuntu, Windows 8 Mobile, iOS/iPhone
Sign up for CIO Asia eNewsletters.