As always, the iPod would be the ultimate....but for <$100 you should be able to get a flash-based player with a removable media slot (typically SM or SD/MMC, occasionally MS or CF). Reliability shouldn't be a problem with a flash-memory player; I haven't had any reliability problems with my MPMan.
How much music depends on compression; I can get about 2.5 hours of music into 96M with 56K bps compression, which sounded fine to me 95% of the time -- but you might feel differently.
Get something with either a belt clip or arm band (e.g. SonicBlue NikePlay, $90 refurb older model, $200 new model).
Good starting points would be a large retailer (e.g. Fry's) or on-line store with a big selection, e.g. here's an [link|http://www.amazon.com/exec/obidos/tg/browse/-/290436/ref=br_bx_c_1_3/103-6322146-3109422|Amazon link]
Tony