Been reflecting a little - actually there is a useful app - MM Tracks (mentioned above) that enables use of Memory Map OS maps on the phone (with a BIG SD card I have the whole of the UK) - downside is that Mr Memory Map doesn't like it and the latest range of maps don't work ... you need the versions that came on CD, not as downloads, for it work
+1 for this. It's an excellent augmentation to an eTrex, as memory map is much better for quickly scrolling around and getting a bigger picture of an area. The battery life's still pants if you try to use it continuously, as the screen draws a fair bit of power, but it's perfectly usable for quick checks, and assuming you have a power sorce, a viable alternative to carrying a stack of OS maps on a long tour.
"OSMAnd" is an Openstreetmap client that allows you to use maps offline. Not OS map quality, but does the same sort of thing, for free.
Google maps, fairly obviously, relies on the network to download maps. This makes it power-hungry and unreliable (you often need maps where there's no signal). Latitude tracking is unfit for purpose on Android, as it only updates your location while the maps app is active in the foreground. If you want to use Latitude for tracking, get a Nokia.
I found the Boris Bike app ("Barclays Bikes" I think it's called) useful, as the holes in my head are unable to detect nearby bike docks through solid concrete. This is, IMHO, the sort of thing smartphone apps excel at. If you want a navigator/logger, get a Garmin.
"Tasker" deserves honourable mention. While not actually a GPS app (it's a utility for scripting all kinds of Android functions), it can be used to achieve advanced levels of power management (eg. coming out of airplane mode once every half an hour to check for messages), and to script GPS logging or tracking.