Generally, I'd stay away from any sort of HD players because Hard discs are a bit of a fuzzy lot. I know they're engineered such that they are less prone to head crashes during movement, but given enough shock and forces that a player may encounter during an exercise regiment the chances are still there that the drive may and can experience a head crash. Once that happens, you're out $250-400 depending on what you've paid for.
So, the best choice would be to use a flash based player. If you're looking for a budget choice, you can grab a 128MB one these days for $100ish depending on the brand and features. For 256MB players, I'd say anywhere between $150-175, 200 max. $300 should net you a 512MB Flash player (I believe...), which is pretty close to what a CD full of MP3 can hold (give or take about 2-4 hours of playback, depending on your compression settings).
Now, if you must get yourself a HD player, a $300 can net you a 40GB Creative Zen NX jukebox, which is a fantastic deal (considering iHP-20 20GB and iPod goes for around $350-400ish, depending on the retailer). For the mini-HD players, you can have one for $200, which nets you on average a 1.5GB player.
Finally, if you're lucky enough to score a MuVo2 4 GB player ($200? $300?), it can be disassembled for its Hard Disc inside, which by itself fetches around $400. A nice thing about this particular player is that once you've freed the Hard Disc, it can be replaced with a mere Compact Flash cards, which are dirt cheap as far as flash memories are concerned (I've seen 128MBs for less than $30). Grabbing this player, however, involved a high degree of luck and karma it seems.
One more alternative (monkey wrench): If you don't mind MiniDiscs, the current generation of players can be had for $100-$150, the new HiMDs come $200-$400. HiMDs might be suitable for your needs-each HiMD discs holds 1GB of data. However, if your library is chock full of MP3s, you'll not only have those files transcoded to ATRAC3/plus but use SonicStage software to transfer music to the HiMD device. That is your call, but you like drag and drop, then I suspect HiMD won't be the device of your choice.
Shop for a Flash MP3 players, google around a bit, and you'll find something to your liking.