The question is what data is Google getting from your phone, and how is it using it.
If it gets that you searched for a particular address in Maps, that's one thing, but if all it got is that a search was made for a house number in a given area, that's another. (There are areas in which Maps shows only empty space. If a lot of people are searching for locations in a space like that, maybe they'll increase the map granularity for that area.) I have no problem with Google knowing that a phone was used to perform a function, I do have a problem with Google knowing that I searched for a particular item or street address. Are they collecting statistics or personal data?
Google is definitely collecting personal data and building a profile on you. They do this so they can target ads to you. You can actually see (almost) everything Google collects in you go to your Google Dashboard. And Google actually allows you to delete it.
Most people don't understand Google's business model. One common misconception is that Google sells your personal data. They absolutely do not. Your personal data is their competitive advantage. What Google does is sell targeted ads. To explain this we need some background.
Back in the old days companies would buy ads in print, radio, and TV. The only data that was available was the total number of readers/viewers. So whatever medium (channel, station, magazine, etc) could deliver the most people could demand top dollar for ads. Later people started collecting basic statistics and demographics on readers/viewers (think Nielsen ratings). So companies were able to design targeted ads. They could say, I want my ad to be seen by african-american males between 25 and 34.
Google has taken this to the next level with their information collection. Companies can approach Google and say "I want my ads to be seen be caucasian soccer moms between 28 and 30 who have a annual household income of between $80k and $100k, who have purchased a car in the past year and enjoy listening to light rock" and Google can deliver that kind of granularity to ads because of the personal information they collect. And because they can do this they can demand TOP dollar for ads. In theory this also creates a better experience for users because we see ads that we're actually interested in. (That's debatable.)
So yes, Google collects a TON of personal information. No, they don't sell it or share it; in fact they guard it like their business depends on it (because it does). And in exchange for all this personal information they provide users with a ton of free services to keep them coming back. You have to decide if it's worth it to you.