Navit or anything that uses OpenStreet Map as a the backend is probably the ideal, however there are places which are lacking data.

We were talking after the summit about producing a routing and tile generation server for Maemo mapper which was to use OSM data (and therefore be able to work off-line) but I, for one, have been pretty busy and it's slipped down the todo list. Interested?