The lack of GPS is the killer for the N73. It's a proper PITA trying to keep both the phone and the separate receiver charged.
A mate has a Nokia N95 which has an excellent GPS receiver. Quite easily finds an accurate GPS signal indoors and away from windows. Only downside appears to be that it has no SD card slot for extra memory so you need to connect to a PC to transfer large amounts of data quickly.
I'll probably go for the N96 but I want to see what I'm getting for the money and how much of the features are extra, i.e voice directions appear to be a paid option on the N96 and it seems only the 6210 has the built-in compass if that's important to you.
Nokia UK - Nokia N96
There's also the 6110 which looks a little more robust than the N96 but has a small screen. You pay your money..., etc
Nokia UK - Nokia 6110 navigator
Either way, I'll still be running TomTom Navigator on it in addition to the Nokia Maps software.