So far I've tried:
Nokia Maps 2
Tomtom 6
Garmin XT
Route 66 (on my wifes' 6110)
Each one of them have some stuff I like and some stuff I don't like. Ideally we need a combination of the bunch - Garmin (maps, graphically) with the Tomtom search and status bar.
Nokia Maps
Came free with phone and new maps can be downloaded for free.
Least accurate maps (should change soon now that Nokia owns Navteq)
Cannot figure out how to change away from North-Up view
Pretty basic features
TomTom

Easiest search
Fast
Best interface while navigating

Voice prompt gets a bit annoying (warns you several times NOT to take an off-ramp on the highway)
Don't like the process to enable internal GPS everytime
Map is rather basic (graphically)
Menu could be better
Insists on switching the sound on when you press a key on the phone
Garmin XT

Best looking (graphically)
Maps for SA very easy to find
Losts of resources (Mapsource ! SA POIs)
Custom vehicles
Search results sorted by how near it is

Crashes from time-to-time
Should make better use of shortcuts for often use functions
Should be able to customize statusbar (like tomtom)
Doesn't always show other street names
Route 66

Easy search (free text)

Maps that came with the phone was pretty old and they want to charge 50 Euro for a updated map
So far, I personally think Garmin is that best and hopefully the next version will be even better.