I debated and researched these things about a year ago.
I decided to go with a CD-ROM based MP3 player for several reasons.
1 - Price...way less expensive than the HD based and Memory Chip based units.
2 - Durability...no spinning HD to worry about getting trashed from vibration.
3 - Convenience...though you CAN load a full 20gb drive with a LOT of MP3's - programming various playlists can be a real pain in the arse. I've got several CD's that I simply dragged and dropped MP3's onto with whatever flavor of tunes I wanted to put on them. Each CD can hold something like 20+ hrs of CD quality MP3's.
3a - Memory Chips just don't hold enough tunes unless you've got bags of dough to spend on 256mb or bigger chips. CD's are simply DIRT cheap by comparison!
4 - I use recharchable NiMh AA's and they last for about 20 hours!
I ride VERY rough, VERY rocky technical terrain and mine RARELY skips!