Well I would say Google Navigation does "well" because it is the default on all Android phones. From the free on contract special to the $600 flavor of the weak (pun intended). Since Android users aren't known for spending much (if any) on apps, they are content with whatever is pre-loaded on the device for the most part. Apple users think a bit differently.
I have used Google Nav in the past myself but that requirement of a data connection is a real killer...unless you are in the big city and stay there. Once you get outside it becomes pretty worthless and having a navigation app with maps and POI on-board becomes a necessity.
I also prefer Navigon for my iPhone navigation needs, though I also have used Motion-X (requires data, though you can preload maps) and TomTom in the past.