Sorry...don't really have any suggestions for you! I do own a Rio 500 which I got a LOOOONG time ago because it came packaged with a CD Burner. It's a fairly good mp3 player. I used it quite a bit back in the day while running or working out. Haven't used it in some time now.
The Rio player is good and it's probably very cheap now. It only has 64mb built in though. You can check out www.epinions.com They have reviews on all sorts of stuff there, might be helpful.
The Creative MuVo mp3 player is quite good, its also a USB drive.
No software is needed, you just plug it into a USB port and upload the mp3s onto it and it'll play them. You can get it in 64Mb and 128mb.