The regular version of Google Maps for Android now contains the ability to cache maps for use without an Internet connection. Here's a short video that illustrates its uses. My understanding is that you can save up to six area maps, each up to about 10 square miles, at a time. The app shows how much space it needs to store the map area you've chosen. The maps are available for 150 countries.
With GPS turned on, your location on the map is shown by a blue dot. If your device has a digital compass (magnetometer), the map can orient your direction, too.
No search for an address, and no turn by turn navigation while offline, but you can't have everything for free.
An updated Maps for iOS devices is coming "soon."