What Android geocaching apps have you tried? I believe all of them (CacheMate, GeGeo, GeoBeagle, Geocacher, Geodroid) can do live searches based on your location. Of course, these are all web-based searches. Groudspeak will eventually release an Android app with direct database access. There are other apps in the works as well. CacheMate has by far the most functionality of any existing smartphone geocaching app.
None of the examples above are "best". I have tried them all and the best is: GeOrg. Look here: GeOrg by Ranitos
They even have a solution to get data without going through the web interface. They call it "connectors", but since they haven't got any answer yet from Groundspeak whether this is legal or not, they haven't implemented it directly in the app. You have to do some programming on your own and I’m not qualified or haven't done enough research concerning this matter.
Another promising geocache app that could be very nice is "GcDroid"! Download it from the Market. :-)