You might want to actually try using gpsdrive before presenting it as an example of a good software experience. (oh, the memories...) While they had a release in 2010, I don't think much has changed since 2004. It was certainly best-in-class in 2004!
The best OSM navigation tool I've found is called OSMAnd but it's still quite painful. Terrible address/city lookup, poor route selection (sometimes abysmal), difficult UI. I wish I could rely upon it but I just can't. I'm using Google Maps all the time.
For the past decade (since Bruce Perens was working with the Tiger data in 1999?), the year of solid Linux/OSM navigation has seemed pretty close. Just like the year of the Linux desktop, it's only a couple of years out! Too bad it seems to be constant time to completion.