Mp3 CD player should be the way to go. i own the RioVolt SP-100 (IIRC), and it supports MP3, WMA, and CD-Audio out of the box, and with a firmware patch it also supports M3U. i can't say anything about the battery's, since i only use it on the mains. but it's great, and if you get the SP-250, you also get AM/FM support. you fit about 12CD's on one disc, (depending on compression offcourse) so that shouldn't be a problem. it also supports directorys very well, you can browse them just as good as you can in explorer using the keyboard.
or you could do something with an HD, with the added advantage of an external HD for transporting huge files CD's couldn't handle. but with a cd thingy, you can also play plain audio CD's, so you can keep using any cd's you might already have.