There are a bunch of apps which would match your description. Some of them come for free, some require a little fee:
OsmAnd
Available in a free version and a paid version (~EUR 3.50) at playstore, and the latter one also for free at F-Droid, this is one of the best known high-quality solutions for Android. Map material can be downloaded per-country for free and then be used offline to navigate. Plenty of plugins, e.g. for parking.

OsmAnd offers offline navigation (incl. voice guidance), special modes for hiking, public transports, skiing, nautical, … and includes a lot of other sources. Material is based on OpenStreetMap, a community project.
Locus Map
A bit more costly, Locus has a free version and a paid version (currently ~EUR 8.50) at Google Play. I'm using the latter for years and am quite happy with it: Many different map sources (including those from OpenStreetMap), a lot of useful addons, even supports the Pebble so you get navigation on your wrist. Maps cannot only be downloaded by country, you even can define your wanted area free-hand – e.g. a 10km stripe along the road you want to take. Turn-by-turn navigation, tracking, geo-caching and much more is supported here.

Both are good choices. And there are many more to chose from in my app list.