I'm using Marble, which can use on-board maps and has voice navigation, although I haven't tested the latter yet (got to download and convert some voice files from my tomtom.. some day..

It also has offline navigation, but needs a connection in order to convert the address you give into coordinates (offline routing maps don't have street names, etc.).

With the latest version (1.1.1) this is supposedly implemented, but needs some updates to the routing maps (which are not the same as the displayed maps).

Sorry the information is a bit fuzzy, but I'm just starting to use Marble..