[kscz]

How about Open Street Map? http://osmand.net

It's not perfect, but it provides a good base of functionality, and gets you to big tour destinations. It will also get you to most restaurants in a big city, but it doesn't have hours of operation or star ratings, so it's less useful in that regard.

I wish there were more alternatives to Google Maps though. You're absolutely right that it feels indispensable to most people these days...

[danjoc]

That one is unusable to me. I nearly throw my phone in frustration just trying to enter the destination. Region, City, Street, Building... wtf? Not only backwards, but four fields. Can't even search by destinations, like "Pi-hi cafe". You can enter fields, which never even works, or stick a pin on the map. It makes me furious just thinking about how awful it is.

[girzel]

The new version of the Osmand~ Android app introduced free-form text searching.

It's a lot better, but still not good.

[marssaxman]

Google Maps actually feels unusable to me these days, not indispensible! I don't know what Google was trying to accomplish with their last UI rework, but I can't stand using it anymore. I actually switched to Bing maps, because it was stupider, less helpful, and therefore more likely to give me the information I'm looking for.