You don’t need a PDA for GPS, but you may want one if money’s not too important, or you already have one.
I’ve got 2 gps receivers, both should be available for about $100. My handheld one is a Magellan 315, and the one for my car is the RandMcNally receiver only (useless without a computer).
Any GPS receiver you get today should provide sub-10-meter accuracy, since selective availability has been shut off. If you’re really really going for accuracy, you need to consider DGPS. Differential GPS recievers use the normal satellites as well as ground based correction stations to provide a very accurate fix. If realtime coordinates are not incredibly important, then you can use post-processing of recorded normal GPS readings to get DGPS accuracy.
Any modern handheld receiver should allow you to up and download waypoints and routes, and record/playback positions. Garmin and Magellan are very good brands. All you have to do is decide how many waypoints and other things you want to be able to store, then find the receiver that meets those qualifications.
My dad has a more expensive receiver that has a slot for map cartridges so he can actually have a moving map display on his receiver. The same can be done with the various PDA gps units (handygps, geode, magellan has one).
Bottom line is that most commercial receivers will probably do just fine for you.
Oh, and check out http://www.geocaching.com for some fun.