There are quite a few alternatives for downloading and storing maps on Android. Some of these are more GPS than turn by turn Sat Nav but a couple of suggestions. Most have demo/free option so you can try them out.
Locus is a free app that supports several different map formats including OSM, Bing etc. You can create maps on PC and transfer them, works well with geocaching apps as it supports queries etc.
A hacked version of Google Maps called
brut that enables maps to be downloaded offline and used in the app. I know it is highly thought of over on XDA but I have not used this app much.
MM Tracker displays Memory Map qct files. There is a free version to check it works on your phone first. I use this with Memory Map for OS maps.
OSM And is an OSM based app that features navigation although I have not used this one.