What I've done (twice now) is buy the largest single drive player available.
The theory is that by the time I've actually ripped that much of my CD collection, drive capacities will have doubled. This was almost true. I had nearly filled my 10G Mk.I when my 18G Mk.II arrived.

Once I fill up the 18G, I'll look at the state of the art, and act accordingly. (Those 25G TravelStars are looking good, but in three months, they'll probably be at 40G.) Though SoundJam MP has sufficiently automated the ripping that the drives fill up fast these days. ;)
As for the Mk. I....Hey Hugo, am I going to need to patch the kernel to go beyond 32GB/drive? I've given serious thought to building the Mk.I into an enclosure with space for four 3.5" drives, and add Maxtor monster-of-the-week drives as needed. Of course, since the Mk.I doesn't have ethernet, to make this useful I'll need to put some minimal host in the enclosure too...anyone have PPP over USB working?

-Zandr
Mk.I #150
Mk.II #39