I bought a 20 GB RioRiot, and left it on an airplane. I ended up replacing it with a 10 GB Windows iPod. If I did it all again, I'd skip the RioRiot. The user interface on the iPod is sooooo much better. The RioRiot took me several days of consulting with their thick manual to get sound. The iPod took 5 min. Also, in terms of music management, the RioRiot didn't let you download playlists! While you could define them once the data was downloaded, its a stupid omission. Also the firewire on the iPod is significantly faster--a real consideration when downloading GBs of data.
The size of your mp3s is variable--I think 128 kbps mp3s average about a megabyte/min. While people using mp3s for home audio seem to prefer 320 kbps encoding, that seems to make your mp3s 2.5x larger. There are also various other options for encoding--high/middle/low quality and various permutations on mono/stereo/true stereo. Based on the compromise between data size and quality for an iPod, I encoded my mp3s at 192 kbps, high quality, true stereo.
I just posted another thread looking for advice on creating mp3s. Its a consideration in buying these things--it takes a looooong time to rip your CDs to mp3s. I'm also having a huge problem getting clean rips--I get stutters and background nastiness. Looking for help there...
Good luck.