Try c:geo. I've been using it for a few weeks now and have zero complaints. It links flawlessly for paperless caching with geocaching.com. It allows you to d/l for offline use and gives you the option of many different map types. It's interface is a breeze to use, allows you to use a live map, compass, store caches or navigate using coordinates you input yourself. It also allows you to search based on type, name, address, gc code, trackable, keyword, username, search nearest, etc. It allows you to link with a gps unit through bluetooth, your phones calendar for events, scan geocodes, scan barcodes, or search for geocaches by name. I'm sure I'm missing some things. Best of all, it's free.
