Nokia 6210 Navigator? Seriously, though... I still feel my N95 is the best phone on the market, even 9 months down the line... However, there's a couple of issues to consider:
1. The N95's SatNav (and I believe the 8gb as well) is severely 'broken' out of the box. You have to pay a fee to Nokia to get voice guidance on the integrated Nokia Maps app. Alternately, you've got to get creative & get Garmin MobileXT installed & working...
2. The 6110/6210 (if the latter is available yet) come with fully functional SatNav, albeit Route66 which isn't as good as Garmin/TomTom
3. Phones like the Sony Ericsson P1i come with a separate BlueTooth GPS receiver (sucky) and use software like WayFinder that constantly uses your data/3G/GPRS connection to download maps (even more sucky)
My suggestion would be, unless you want to fiddle with something like the N95 - go Nokia Navigator!