Garmin Geko 201
I had a small Garmin Geko 201. This is not a highly scientific device, but works well for basic things, is simple to use, easy to label, and much smaller (about 1/4 the size/weight) than the other Garmin GPS's.
We used it for tracking roads, marking villages, rivers, and boundaries. It quickly coordinates with satellites and often would be accurate to 9 feet. It does have a limited amount of tracks it will create though (and will start to delete the first tracks if you have too much info). I don't believe a base map can be entered on it, so this is only great for exploring "unknown" lands.
Here's a site for it that gives more info.
Oh, and the Geko also has GPS games if you get bored.