I'll chime in with another vote for the iAudio. (I have the 20GB M5). It'll play Ogg, Flaac, MP3--just about any music file. It's compact (not as small as iPods, but small), good looking, and can take a couple of drops (yes I've dropped it a couple of times) Sound quality is excellent. It is Linux compatible, when you plug it into a USB port it shows up as a harddrive. You can transfer to and from your harddrive, and it plays well with Listen music player (which I prefer over Rythmbox).
I also have good things to say about the M5. My audio files (ogg,flac, and mp3) are already in a nice directory structure, and I like just having to use cp, mv, and rm to manage the files on the device. I'm also happy with the quality of the line in recording, but that requires buying a proprietary dongle for 20 bucks or something. There is no option to record to wav, but at 320kbs, mp3 sounds good enough. I love that the screen has rainbow text which says "COLOUR SOUND" though there's nothing colour about it.