Wow, you asked a lot of questions. I just bought my first mp3 player, so I did some research, and I'll try to answer some of your questions.
There are many different products in the under $250 range, but the question is how much space do you want minimum? If you don't need more than 1GB, I'd go with a Flash player, which stores all your songs in flash memory. Flash is more impact-resistant than HDD memory, which if you jog with it you can permanently ruin your player.
I got a 20Gb Creative Zen Touch from jr.com for $220, including the protection plan I bought for it. My requirements were playlists on the go, 20G of space, and not an iPod. You may have different requirements.