Carrying on this thread: I've tried a few of the Android navigation systems. I already have a Garmin 60Csx (a hand held outdoors unit) and a TomTom satnav so I'm reasonably up to speed on how GPS navigation works. My Android phone can't replace the Garmin entirely for several reasons but it can certainly replace the TomTom.
I've found the accuracy of the GPS signal on the phone and speed of lock to be roughly equivalent to the Garmin 60Csx as well as other information such as speed and altitude. With the right apps installed you can get all the information that a dedicated GPS unit will give you such as satellite positions, accuracy, grid reference, etc.
Most apps use online mapping data. This is a problem if you are out of range of a mobile signal, which you can easily be even in urban areas at times. There are some apps that use maps stored on your phone though and can work entirely offline. If you know you are likely to be in an area with limited or no mobile coverage, and you have Android 2.2 and above, you can cache the maps to your phone in advance by searching for the location you will be at. You then scroll around it so that the maps in the area are stored on your phone. Not ideal and I wouldn't risk my life on it but it does work.
One app that is very interesting is
MM Tracker https://market.android.com/search?q=mm+tracker&c=apps. This app lets you view Memory Maps that you own on your phone. (This is the app Memory Map themselves should be making.) I've been using it and it works well but, being bitmapped maps they don't rotate to follow your direction and they are big so you need lots of storage space. The app also sucks the life out of your battery.
Another good app is
Maverick https://market.android.com/details?id=com.codesector.maverick.full&feature=search_result. This sucks quite a bit of juice from your battery and needs a data connection to get its maps but its an excellent app that gives you lots of GPS data, height speed, altitude, grid reference, compass bearing, etc. If you set your mapping to "Multimap" (NOT OS Explorer) you will get detailed 25k Explorer maps delivered to your phone for free. This app will also let you load a variety of other maps, including Open Street, Google (inc. Sattelite and Terrain), Bing, OSM cycle, OSM public Transport, etc. A superb app but does need a data signal to be able to display maps that aren't cached.
There are also "Satnav" style mapping apps available which will work entirely offline in the same way that TomTom and Garmin do. You buy the maps and store them on your phone. Street maps for all of Europe typically take up about 2 gig of space on your SD card. The app I use is
Co Pilot but there are plenty of others and they may be better but at UK£22.98 for UK maps it's reasonably priced, the latest release will also move to SD. Other apps of the offline car navigation type are Navigon, Aura, NDrive, etc. Co Pilot (and probably others) can be configured for pedestrian, bike, motorbike, public transport and car navigation.
The Android phones come with
Google Maps installed on them and Google Navigation, both of which are very good and they are free but are best for street mapping and do need a data connection. The
Google Navigation is incredibly easy to use and even shows you a Street Map photograph of your destination which is cool, you can use it in satellite or hybrid mode if you are off-road but again you do need to have data reception.
My Tracks is often pre-installed but can be got for free, this will record your tracks and POIs in the same way a handheld GPS unit does.
"Also ran" mapping apps IMHO are
BackCountry Navigator, I didn't get on with it and was more USA based.
GPS Essentials, good app for giving you GPS information such a coordianates, speed, altitude, etc but if you have Maverick installed you don't need it and Maverick is better.
GPS Test gives you basic GPS data. Again if you have Maverick you don't need this app.
Then there's an app with an instantly forgetable name
gvSIG Mini Maps https://market.android.com/details?id=es.prodevelop.gvsig.mini&feature=search_result. This seems good at first but it sucks your battery dry in minutes (Maverick uses less power). Many of the maps aren't relevant to the UK, it won't display the 25k OS maps that Maverick will. It doesn't give you all the GPS data that Maverick does. I did an uninstall of this app after a week or two mostly due to the heavy power usage and the fact that Maverick does it all better and does more.
There are plenty of other apps and some may be better, or more useful to you, than what I use. I don't really have time to try them all but I do recommend
Maverick and
MM Tracker for Bushcrafty type use.
Other apps I might get around to trying are:
Locus, UK Map 3D, Open GPS Tracker, etc. There are almost too many.