Depending on your needs take a look at Mapdroyd. This will give you GPS location and maps but doesn't provide for searching locations or directions--it is a simple map and current location app. It is free and you can select what areas in the world you want to download maps for rather than requiring that you download the entire world.

As the maps are stored on your SD card you do not need any air/data connection, just your GPS turned on.