Someone told me that Locus is an offline navigation/GPS app. Have you looked at it?
I didn't -- I don't have a Bluetooth GPS, so using an offline map won't benefit me (at the end of it, I still need to tether from my phone to get the GPS data.) However, I knew people who tried
iGO My way with Bluetooth GPS on their Nook Color are quite happy with the result. Their major complaint is that the GPS unit has to be very close to the Nook Color (seems to be a problem of the Nook Color -- Bluetooth reception drops significantly beyond 1 ft.)