try out Maverick, there is free version whit just a little restrictions compared to paid. on the settings you can select what maps you want to use, google, nokia ovi, wikimapia, open street maps, and plenty more choices.
theres is also a program for pc where you can select what map areas and zoomlevels you want to download, and then you can compile map cache from them and transfer it to phone, tough its loads of small files, and a pain in the... but you could get the maps of the area you are heading to phone from the pc. looks like caching of google maps is disabled because google requested that.
- about the app
- Mobile Atlas Creator, to create map files on pc for mobile use. also other supported android map apps listed here.
after looking trough those other apps, OruxMaps looks interesting, fully free.