This is a subjective comparison. Also, there are probably errors in it, and I'd love for you to correct them, if you spot anything!
As far as I know, there are five navigation programs that supports/is expected to support S60 3rd. Nav4all, Wayfinder, Navicore, Route 66 and Tomtom (not ready for S60 3rd yet). Only with the two first ones, you don't have to store big map files on your memory card.
Nav4all is free and is still a full-functioning navigator program. It has actually more functions (and spoken languages) than Wayfinder. But the maps are crude (the roads have no width for example) and buggy and the voices are unclear, data sounding. The route calculation is also sometimes strange/very strange. It shows that it is free. But it's acceptable for some use.
Wayfinder (about €149 for Western Europe life-time maps, but you pay extra annually for traffic or speed cameras) is clearly better. It has a strange zoom bug (bug, I'd venture to say) which means that you can't lock the zoom level, it's automatically adjusted to a level that the program finds appropriate. Wayfinder is also critizised for having annoyingly frequent voice prompts. You can't adjust this (but it's one thing that the Wayfinder team is working with right now!). Finally, Wayfinder only has traditional 2D maps, no "Tomtom" 3D maps. The Wayfinder team is considering this. Other than that, Wayfinder is really nice with a clean GUI, also for the 2D vector map!
Navicore is reviewed on http://www.allaboutsymbian.com/forum/showpost.php?p=274921&postcount=14 . From what I understand, it may be better than Wayfinder. Navigation screen displays include 2D and 3D. Voice prompts are more well thought-out. The big problem, as I see it, is that you have to keep maps on the memory card. The following below represents the space it occupies:
Skandinavia 180 Mb
Alps 210 Mb
Benelux 125 Mb
France 252 Mb
Germany 245 Mb
Spain and Portugal 145 Mb
Italy 225 Mb
UK and Ireland 140 Mb
All of Western Europe takes 1522 MB. Therefore, Navicore is personally unusable to me. I will probably stay with Wayfinder. In Sweden, I have a flat rate 3G/gprs data rate and 3G/gprs prices in all of Europe will hopefully go down this winter, because of recent requirements from the EU.
There is Route 66 7.0 which also stores its maps on the memory card. But these maps take even more than the maps of Navicore. Here, most of Europe take 4 GB so you simply can't fit all of it in! You have to load and remove maps on a regular basis if you travel abroad. A review on http://bonte.co.uk/myBlog/?p=168 .
There is no Tomtom 6.0 for Nokia N80 yet. Tomtom also stores map information on memory cards. There is no reason to think that they would be able to fit Western Europe on less than eg. 1 GB either.