Search is of course entirely useless, worse than useless, if you don't know in advance what you are looking for. Needless to say, search is not an adequate substitute for intelligent design and proper levels of detail on maps.
Can you explain your use case here? Normal Google search is great for finding the name of films you can't remember by typing vague descriptions of the plot. Maps has similar functionality, like "local coffeeshops" or "<business> in <city>".
My technique: When I'm in an unfamiliar city, I search for restaurants and then looks for clusters. When you see a cluster of restaurants, this tends to be a downtown and is usually somewhere 'interesting'.
> If you don't actually know what you're even looking for, NO MAP whatsoever will be able to help you.
I use OpenStreetMap for this use case so I can only answer for them, and they seem to do a great job at it. If I am looking for the general shopping area, or office areas, or anything like that, I can zoom and pan through a city and find it very quickly. That Google doesn't show labels anymore makes it completely useless (and I've run into that a few times).