- "Organic Maps" (a fork of the old MapsMe codebase) if you want a clean, simple user experience
- "OSMAnd" if you want a very powerful, highly customizable map application, which comes at the cost of a steeper learning curve
Both apps are open source and support navigation, offline maps and POI search.
The things I miss most compared to Google Maps is live traffic information and the powerful search. However, this has a privacy cost, so I generally try to use OSM first, and only fall back to Google Maps (in the browser) if I really need to.