I got a Sony minidisc walkman and made a velcro armband for it. I record to the disks with Atrac3 132 kbps compression. The blank minidiscs are about 5 blanks for $10, can be write protected, rewritten 1 million times, and don't get scratched like cds.
I run with it everyday. The discs will hold about 2 hrs, 40 minutes (80 min disc) good quality music. The software is easy to use, but is kind of annoying. I've had no problems with ripping to the walkman from cds or MP3s. The battery life is outstanding. At least 10 hours play with 1 AA battery. It has never skipped.
With the 2hr, 40 min capacity, you could run a fast marathon, but most likely you'll run outta music
If you run 15 miles or less, you'll be fine with this.
Hope this helps!