I just picked up a neat gizmo, a Creative MuVo TX. It's a no-nonsense tiny flash-based MP3 player. 256 megs of music, not much bigger than a lighter, 1.5 ounces (42 grams), $127 at Amazon. See this review for details.
What I like best is how simple it is. The core is a USB flash storage unit. Just plug it into your computer and copy files over, no DRM or software nonsense (screw you, iPod). It doubles as a giant floppy disk. Then plug it into the AAA battery (10-14 hours of life) and the headphones and you've got a tiny music player.
The device UI is nice and usable and the sound quality is good. The hardware does feel a bit flimsy, but what do you want at that weight?