Waze is a very popular replacement for Google Maps. It provides users the ability to contribute back to the community by reporting traffic incidents, gas prices, map issues, and so on. While it might not be a household name, it has an impressive track record.
However, if you're de-Google-ifying for the sake of your privacy, you're probably looking for something that won't track you, or doesn't rely on your input for community benefit. In that case, you should check out Eraser Map from Mapzen.
While we believe in open data, some data should not be collected at all. A company we really admire is DuckDuckGo, a search engine that focuses on user privacy. As we saw open data quality improve, we wondered if we could use our SDKs to build a mobile mapping application that could make the same promise as DuckDuckGo: not to log or track our users, at a time when user privacy is a major concern. Since Mapzen runs its own map stack and is not dependent on third-party mapping providers, we can follow through on promises we make about how we handle user data. We even went so far as to create LOST, a drop-in replacement for Google Play Location Services, so your location is kept as private as possible.
I personally don't travel that much - in any case, I only use turn-by-turn navigation if I'm going somewhere I've never been, as I have a pretty good navigational memory. However, I can test the waters of both of these apps as I drive around, as I do quite often. :) Has anyone used either of these and can attest to their reliability? Are there other map services you use or have tried?