I recommend Navit, but you have to dig around in the Navit thread to find links to the latest version (the one in the repos is a bit old).

Cloud GPS is actually coming along nicely, but still no voice navigation. (However it can route internally, instead of having to connect to the internet to find a route.)

Ovi Maps (the preinstalled mapping software) CAN be hacked to be a lot better. There's some development on making it have voice navigation in progress - not the program itself (as it's closed source so we can't modify it) but by making another daemon run in the background that detects when the maps program is about to come to a turn on the route, and plays a sound file.

Then there's Mappero/Maemo Mapper, and a couple of other not-bad programs in development - but they all (some have voice navigation, some don't) can't route internally, they have to connect to the internet to do so.