I need a way (possibly a third-party application) that allows me to use maps and GPS without an Internet connection.
I don't use it by car, just for walking in cities. It would be nice if I could just copy all data relative to a particular city before going there for tourism.
The Google Maps app does not store maps reliably, so it is risky to rely on it without an Internet connection.
Note: many of these applications use map data from a really cool free map project called OSM (OpenStreetMap), which anyone can contribute to. OSM is constantly improving, but in many areas it may lack information like house/building numbers.
There are detailed reviews of many Android GPS apps here: Android Sat Nav Apps
Google Maps 5.0 now supports offline mode!
I haven't had a chance to try it myself yet, but I've heard good things about Maverick:
Maverick for Google Android - Code Sector
There is both a limited free and pay version.
I am now using OsmAnd.
It stores OpenStreetMap maps on the phone's storage.
OsmAnd uses a vectorial format, which means it can store a lot of information without taking too much space, and is visible in all zoom factors.
You can download the maps you want, for instance Italy, Bolivia, or any other country/region.
Free, open source.
I regularly use Locus. It doesn't have much in the way of navigation support (although I think this is in the works), but for off-road and off-line use it's fantastic.
It allows downloading of maps for off-line use, supports SQLite and GEMF maps, which allow large map (2GB limit for SQLite, no realistic limit for GEMF) tile sets on your SD card without wasting masses of space. It also supports vector maps as well as bitmap ones (more coverage, less disk space). It has a very good interface and is well supported.
There's a free version with ads which doesn't support in-app map downloading (I think), although you can use your PC to download the maps. The paid version is not expensive.
That all sounds excessively glowing, so I should emphasise that I'm not the developer and have no affiliation; just a very happy user!
For England and much of Europe, ViewRanger is great. Supports Ordnance Survey and other official-type maps; also some open street map projects. But it is absolutely what I would use -- and do -- if I am hiking with a phone. For Android - ViewRanger
Have You tried Maps With Me? It has a lite (free) version and allows downloading maps for an offline usage. Also it is very fast: in my experience OsmAnd is much slower even with maps downloaded, although it shows more information.
Have you tried BackCountry Navigator?
It has topo maps, open street maps, and aerial photography.
It has a 16 day demo and a paid license.
Maps (-) allows to store maps for offline use from OpenStreetMap, from OpenCycleMap and from Google Maps.
If you are looking for North American maps (and European maps as well I'm told), than I can recommend CoPilot Live. It's not free though.
You might want to use Sygic if you are in India. It comes with free maps.
Mapy.cz is the easiest to use app and now it has all the content of the whole world for download to offline in vectors (which means smaller files).
It is both for cities and tourism. For navigation it currently needs a network, but they claim they'll make it offline as well.
It is free. The world is covered by a great render of OpenStreetMap. The Czech Republic has its own (great) cartographic data.