I have an iRiver: iFP-195 which has 512mb of memory bought for $249.00 on Newegg.com about 6 months ago..
I bought this model because it met specific requirements I was looking for in an mp3 player:
1)Flash memory vs. Microdrive
I needed a device that would not skip or break during physical activity such as walking/jogging/jumping etc.
i.e. I needed solid state flash memory and not a hard drive.
2)AA battery vs. Rechargeable
When my battery dies I can't stop using the device to plug it into the wall for several hours of charging.
I wanted the flexibility to switch out batteries immediately.
1 Duracell AA lasts about 15-20 hours of continuous play.
Using rechargeable AA's sweetens the deal.
3)Size
The device had to be concealable, so that I can use it at work without my boss noticing.
The iRiver fits in my pocket. It also comes with an armband, belt case, AND necklace.
4)Memory Size
Storage space is the sacrifice of choosing flash memory. Microdrives offer 1-20GB! of storage. Flash players are paltry in comparison. With 512mb on my player I can store about 3-5 full albums, or 1 entire audiobook (~40 mp3 files @45 min. ea.)
However, I use my player on a 12 hour night shift with an earbud in my left ear, and I rarely play my entire memory (depends on the encoding of the mp3). Even if I did run out of playback, the iRiver i195 comes with a built-in radio receiver, which works very well. In fact, I listen to the radio for the first hour of my shift (murder mystery theater,

)
If you don't mind replacing your playlist every day, then
512mb is just enough space to be useful.
The newer iRiver products, the 500, 700 and 800 series flash players, come with up to 1GB of storage. The
IFP799T 1GB is a
significant upgrade of the iFP-195. Most notably it has double the memory and can be used as a USB drive to transfer files, which the i195 can only do only after much difficulty. It costs $355.55 from newegg.com, and would be my choice if I were buying today.
You simply need to decide how you want to use your mp3 player, and buy based on that decision.
::edited for grammar::