I prefer NavDroyd. Although this App isn't free, but it has a nice 3D navigation feature with turn by turn talking voice. Maps are downloaded as vector and have a small size for a big region like a country. It also has a "Add pin" feature for adding unmapped POI's. MapDroyd is the same with similar interface except 3D navigation.
At second place I like to use Maverick. This App uses bitmaps and consumes huge amount of SD card, but has a nice feature: uploading recorded tracks to www.GPSies.com directly :)