The only good cheap solution in my opinion would be to buy a
Creative Nano Plus. Its basically a updated version of what gaming recommended. Its flash based but the highest capacity available is 1GB. I happen to own one for exercising purposes and it sounds great!
I would also recommend that you find a iRiver H1xx series player, if you can find it (only bad thing about it is that its HD based.) I still have mine after 3 years of constant use, so I know its damn durable. Much like the creative player you just drag and drop the songs you want through windows explorer, which is how I prefer it. Too bad the paint on my player is finally starting to chip away but I've read a few tutorials on how to repaint it. If need be =p.
Jam it back in, in the dark.
85242
35212
Kairyu