I've been using a Samsung YP-T10 for the last 2(ish) years, and it's still working perfectly. It's got "only" 8GB of memory IIRC, but that's more than enough to suit my needs. It's inexpensive, it weighs and is a similar size to the iPod Nano, but with a seriously sexy look, and nice, responsive touch screen. Simple operation, access to the full filesystem on the device
, and best yet... It's always worked instantly on plugging in with Ubuntu Linux for me.
It doesn't require a specific program to put your music on it, you can use it like a USB drive, storing whatever data you want on it, even if the device itself can't use the file, it has a customisable interface, can play high-quality video, go pretty damn loud, AND has full advanced audio settings, you name it.
And they didn't pay me a penny to say that...