I'd also say the iPod shuffle.
PC Magazine has a great editorial on a bunch of sound quality testing they did on a bunch of mp3 players, and the shuffle was on top, with what they claim is the most perfect sound out of an mp3 player (and they don't just love apple, the mini was absolutely last on the list, worst sound)
The shuffle is small, cheap, and really with only 512mb - 1gb of space (120-240 songs, sounding nice) you can just pick your absolute favorites, meaning that you usually know what the songs are without looking, and won't have to skip alot.
My sister loves hers.