Organic Maps is one of the few applications nowadays that supports 100% of features without an active Internet connection. Install Organic Maps, download maps, throw away your SIM card, and go for a long trip on a single battery charge without any byte sent to the network.
I’ve always had issues with this app. I think the issue was not every store or address was listed and if it did have it, then it would take forever to load the route to get there.