Google turn by turn navigation on the Motorola Droid works great, they even have a window mount for your car. I guess it depends on the screen size of the phone. Obviously, phones with a smaller display screen won't be very suited for GPS navigation.
I'm definitely happy to see more free GPS apps coming to market.
And I wouldn't say Nokia's free GPS offering was "game changing". The free Google GPS app was the game changer.