I use a rooted T-mobile G1 with Cyanogen 6.0 (a replacement for the stock OS). I tried several map/GPS related applications, such as Mytracks (Googgle), Backcountry Navigator, TrekBuddy, OruxMaps, GPS Tracker etc. The more or less full list of Android can be found on the following web page:
It lists the majority of mapping/logging applications available for Android with screenshots, descriptions, etc.
My favorite app is OruxMaps, this is not a navigation software but it allows you to follow the route, search a point on a map using coordinates in different formats, use online and offline maps, create log tracks in GPX and KLM formats and more. The application is free but is worth donating.
It should be noted that the battery life is not the strongest side of my smartphone. I use an extended battery (2700 mA) plus I carry an additional stock battery (1050 mA), sometimes 2 (with a compass and a paper map in the backpack) just in case. I would expect the phone to be working (OruxMaps, GPS logging, extended battery) no more than 15-17 hours at best. But that's a brutal mode, normally you just want to use it as an advanced compass to know where you are on the map, be sure that you stay on the course, figure out where to go etc - in this mode the phone would work up to 1.5 days (approx, depends on many factors).
Last weekend (Sunday) the phone was about 4 hours under pouring rain in a Chinook plastic case (a great case allowing you to use the phone touchscreen under such extreme conditions, but it can be different if the temp is really low). And it seems the humidity made it reboot once - I was surprised since I have never seen that before.
And last but not least - You can geocache using the smartphone, there are apps for smartphone allowing you to download the coordinates of the geocaches in the area where you are hiking. It's even possible to send coordinates from the geocaching program to OruxMaps on the go - I like that! Just for your info, the attached picture shows the hidden geocaches hidden around Buntzen lake.