If you're in Android use OsmAnd! It's great. It uses data from OpenStreetMaps. It does decent road and walking directions, in fact it tends to do far better at foot paths. You can download whichever regions you want for offline use. The only gap I have found vs Google Maps is transit directions.
Actually, there is: traffic data.
That could be an optional enhancement. And it still does not require your exact position to be sent to Google.
It requires the route you will take and the time at which you are estimated to be at certain points along it. I would say that this is even worse than your current exact position.
No, it does not require that at all. You can implement it that way, but you can also just request traffic information for a whole 'cell' without revealing your exact location, just a cell ID, then do the processing locally.
I'm fairly sure if you have the app on your phone you can download the map data and use it offline unless it changed (It's been a while since I've done it).
They expire in about a month, and then the app will refuse to let you use that data. You should treat it as a cache, not as an offline map.
If you want true offline map, you'd need to use Bing, HERE or OSM.