I think Nokia maps is less accurate, and I find it annoying how it always wants to 'snap' you onto a road, even if you're not. Google's 'circle of confidence' is much more useful.
Is Nokia Maps really clever enough to estimate your positiong based on phone masts? Perhaps I've been too impatient with it...
It wraps text really badly for any roads that weren't originally built by Romans - it's mainly an aesthetic complaint, but a map *should* present the info as clearly as possible so that it's easily understood.
Also, the zoom in and out shouldn't be * or #, (at least not on a slide phone eg N96). My N96 is dying to fall out of my hands when I'm holding it one handed and pressing * or #.
It also zooms too slowly - it should take bigger steps when you zoom in or out.
It wastes *so* much space with the large text at the top of the screen saying "High Street" or whatever. It then devotes half a centimetre at the bottom of the screen to tell you what the two softkeys do, and you can't switch this off. And then there's the everpresent search box. When I'm looking at a screen about the size of a mini playing card, I want as much screen real estate as possible!
That said, voice navigation for the once-a-year that I'm driving is pretty cool...