We use a Palm Tungsten E2 and really like it. In past threads about going paperless, people have mentioned the Palm Z22, which I see is going for about $66 on eBay.

It's a good basic PDA, and will do what you need for geocaching.

If you want something a little better, start first by considering expandable memory options. That will allow you to keep LOTS of data on your PDA. Wireless is nice too.