I as going to suggest the Garmin Nuvi 500. It is definitely paperless. And totally touch screen.
But it does have some issues. I'm going to list these just in case a Garmin rep reads this.
1) If the cache name is too long (haven't tested to find the max length yet) it will shut down the Nuvi when you select it.
2) It has no place to attach a lanyard. That means you carry it all the time and...
3) at least once a caching session I accidently touch the on/off button on the top corner and shut it down.
4) The "save to favorites" is too easy to accidently hit as you use your fingers to scroll the map.
5) It would be nice to be able to have a cache you have tagged as DNF to not appear in the not found list. I'm not going to look for it a second time in the same outing. It would be nice to not have to skip over these when selecting the next cache.
6) It would be nice to be able to delete the GPX files on the divice rather than having to attaching to a PC and using Explorer.
Other than those really minor things it works great. I used it exclusively on a geocaching road trip from San Diego to Mingo and back this last summer. And we just made a caching trip this last weekend to Vegas and back. Only when the cache name was obviously going to be too long did we switch to the phone GPS.