As for software on the OpenPandora, I think the most likely candidates are:
Navit, an opensource turn-by-turn navigation system.
and
TangoGPS, an opensource map.
Both have been ported to ARM systems (OpenMoko for one) and can utilize many maps, including OpenStreetMaps.
I'm not sure on the...