In the previous posts I missed the two vector map choices you have. Fundamentally vector representation of the map should be the way to go, if you need to preload larger area into your phone.
Choice number 1: Osm-android. This is an early stage project. To use it you have to check out source code of the converter application and build it. The converter is quite rough (no GUI). It can only process small countries and I had to fix a couple of issues with it before successfully getting a binary equivalent of an openstreetmap xml file. Visual quality of the map rendered on the phone is poor. But I once tried it on a trip to a semi-familiar neighborhood and it helped me to find my way after missing a turn! Still, this option is probably not the way to go for the most of the people. The biggest advantage of this application is, that it's the only java - android code I found tackling the problem of vector map rendering on an Android device.
Lately I discovered a much more feasible option called Navit. I'll cover Navit in the next blog post.