MapDroyd
I like it when I think that an app should exist and then find that it does. That’s what happened when I realized that a) I couldn’t use my phone’s GPS capabilities with its native (Google Maps) map application without a data connection and b) that it should be possible to download maps that work with GPS but no data connection.
The answer: MapDroyd. It does precisely that, letting you download vector maps to your phone and see where you are on them. I’ve used it a little bit over the last three days, and it’s been pretty good. There have been a few odd bits on the maps—a major street in central Manchester appeared to be missing, for example—but overall it’s been great, and the utility of having maps of more or less everywhere that can point to where you are on them should not be underestimated.