Hiking Navigation.

Does anybody have any experience with a good navigation map for hiking? Obviously it would have to work without a data connection, and it would also be sweet to find something that doesn't drain the battery.
Even an app that would just give me latitude and longitude to use in conjunction with my current collection of paper maps would work.
Since I have the phone I'd like to be able to ditch the Garmin.
I'm using a Nexus 4 if that makes a difference.

There are lots of options on Play, but I'd like to hear from someone with actual experience before I spend money of something.

Thanks in advance.