I see RMaps is not mentioned here yet. I use it when I'm out of the country and want to quickly find out where I am, it can use offline maps downloaded on a PC (stored in some kind of sql database file which speeds things up a lot!), navigation works when there is data connection available, offline maps do support POI's and they can be edited/added/removed on-the-go.
Map downloads support Google maps, MS maps, Yahoo maps, Yandex Maps etc.
Also supports map orientation (direction/compass)
Not ideal for use while driving, but rules for traveling on foot! ^_^