MSI MegaStick 528
This simple MP3 player with 512MB of memory works without problem, the USB (2.0) mass storage is indeed supported. Directories are supported also, the only drawback is the absence of RDS. The biggest advantage over other players is that the USB connector is always with you - it flip-opens from the player, so you don't need cable everytime you want to download data.
I created a small utility called pbm2mlg for creating startup logos for this little one under Linux.
A-Data MyFlash PD0
This is just a common USB 2.0 mass storage flash drive, which happens to be ultra-small. I highly recommend this one - it can be really attached to your keychain without even noticing that and the price is pretty low also.