I was researching what to use instead of road and travel maps on paper with my Android phone.
At home Google Maps works just fine. However the data roaming charges immediately rule out this solution when abroad.
If you would like to spend from 40 EUR to 90 EUR you can purchase offline navigation from Sygic: http://www.sygic.com/index.php/en/how-to-buy.html. The price depends on maps coverage. All the maps they have would run you 488 EUR.
There are probably other offline options but they seem to be bound to some mobile operator and are quite difficult to purchase.
So I looked at the free offerings. The options which are not violating Google's or somebody else's TOS are bound to be based on OpenStreetMap data. OpeStreetMap is a world wiki map founded in 2004. It has gone a long way in terms of coverage, data amount and infrastructure reliability during it's history. Many areas are very thoroughly mapped. The biggest problem for our use case I see is spotty quality of house numbers. However roads, cities, streets and streetnames data should in most cases allow for adequate replacement of travel and road maps on paper.
Another thing which is preventing free solutions to compete with established turn-by-turn voice navigation is a lack of free and quality routing data. This is probably going to be true for some more time to come. That's also why I have little hope for a free solution to compete with established vendors of turn by turn navigations.
Before we look at the free options let's define some terms.
Geocoding - process of translating textual representation of place to it's geographic coordinates. Whenever you use text "search" or something similar geocoding is necessary step to show you the place on map.
Vector map data - Just a bunch of points, lines and attributes. Advantage: map data of Germany weight around 200-300 MB.
Raster map data - The data is stored in form of final images. Advantage: no rendering needed on the device. Major drawback among others: map data of Germany down to low resolution streetlevel weight around 15 GB.
This application is no longer actively developed and the geocoding functionality never worked for me. Another problem with the geocoding service is that it seems to be online-only. The nice part of this application is an option to preload displayed area to the memory card of the phone. You can move to the area of interest and choose what level of details you need for the area. Then just tap "preload" from map menu and the raster tiles start to flow into your phone. This is the most intuitive way of downloading the region of interest. The lack of geocoding functionality is bad. However I still was able to use this program. Before my trip to Budapest I downloaded the region, and found the addresses I needed using Google Maps at home. Then, inside AndNav2 I created favorites of the places and off I went. This was sufficient not to get lost while moving between trainstation, hotel and some landmarks. Not the most comfortable and flexible solution but the program helped a lot. Basic navigation, zooming and compass functions of the program are functional and nice. Another strange thing with this program is that you can't really get it from any official source. The application is not in Android Market anymore and the official homapage offers only broken links for downloading the apk file. To get the application APK head here: http://andnav2-download.blogspot.com
Pros: Intuitive map download - preload
Cons: non-functional geocoding, not developed any more, broken download links, raster data
This is a nice application. You can download and install it from Android Market. To use geocoding you have to download indexes through the application menu. There is a small problem for first time user, though. The list of world regions to download has several hundred items which is quite intimidating. After you fight through the list and download the indexes you need you are only half done with preparations for offline usage. The biggest drawback of the program for me is the need to download the map tiles with your computer. The toolto do it is called OsmAnd Map Creator. It's a Java (cross-platform) program and is quite intutive.
After these preparations you can start using the map in offline mode. The address search as well as the map display and navigation are intuitive and work fine. Compass is missing.
Pros: usable offline map and offline geocoding
Cons: need for a external computer program, raster data
This application is free of charge but it's not opensource. It's actually a teaser for other applications of the same vendor. It has no geocoding and no favorites, so it's usefulnes as paper map replacement is limited. However it has in-phone user interface to download vector maps of the countries you need. As a basic tool to navigate around a city it might be sufficient. I tried to use it during my trip to Birmingham, but with little success. I couldn't really tell which way to walk. Incomplete rendering, non-intuitive compass mode and incomplete OSM data in this area might all have contributed to this.
Basic tool to display online OpenStreetMap data. No geocoding, no favorites, no POIs.