Google Maps can store maps for many locations on your phone for offline viewing, but only in small blocks, which may not be enough for you. It doesn't have true offline navigation either, because you need to connect with Google to calculate your route.
Enter the alternatives: Locus, OsmAnd, and Route 66.
Locus can show maps from many different sources with the Map Tweak addon. Google Maps, Nokia Maps, Bing, Yahoo, Open Street Maps, MapQuest, and many more. It doesn't do true offline navigation, but it lets you calculate routes online and save them for offline use. Unfortunately that only works in the paid version.
What makes the free version of Locus unique is that it lets you download maps from all its online sources to your phone for offline browsing, with a limit of 10.000 map tiles per day. This is nowhere near enough to cover a city like Paris or London in sufficient detail, because you really need the maximum zoom level for all those tiny little streets and alleys. However, if you manage to grab an old copy (v1.9.4 or older), the limit is 25.000 tiles which covers cities like Amsterdam or Lisbon, and Paris within the Périphérique. If you want the suburbs as well you'll have to finish your download the next day, but that's still better than grabbing the bits and pieces over a week with the new 10.000 tile limit.
I run the latest version of Locus, but whenever I want to download a map I load up my old Locus v1.9.4 from my Titanium backup. When I'm done downloading I restore the new version. You don't need Titanium, you can use MyBackup too.
The free version of Locus has a very annoying ad banner on the map screen that's easily tapped by accident. When the ads can't be downloaded because there's no internet connection or if you run an ad blocker like AdAway they are replaced by an advertisement for the paid version of Locus, but not in all versions. Sometimes the screen stays fully free of advertising.
Locus has vector maps too, but they come from Open Street Maps and they're only useful with a paid addon. They render real slow too.
• Locus (Android Market)
• Locus Map Tweak addon (Android Market) to get more maps sources
• Locus v1.9.4 for the old 25.000 map tile downloads (let me know if you're interested and I'll share the APK)
OsmAnd uses vector maps from Open Street Maps. Too bad if your region of interest is outside the USA or northern Europe, because in the rest of the world OSM is often full of blank spots outside the major cities. On the bright side, OsmAnd has true offline navigation. You'll need to pay if you want all the features of the latest version, but downloading maps for offline use and offline navigation works pretty well in the free
Update: offline navigation works in the free version from the
• OsmAnd and OsmAnd+ for free
It took Route 66 ages to build an Android version, but now that it hit the Android Market it's worth a try. The maps in Route 66 are usually way better than Open Street Maps, and its vector maps size is quite friendly to your SD card limits. You get a month of free offline navigation too, and it works very well. After the free trial runs out navigation becomes very expensive, but if you don't pay you get to keep the free offline maps to browse. My advice: install Route 66 before you go on vacation to get the maximum out of your free month.
• Route 66 (Android Market)