I have one which I use when cycling.
It is made by LG, cost about £80, and I bought it from Dixons. (18 months ago)
It's less than 3 inches square, less than half an inch thick, and weighs almost nothing at all, so it slips easily into any pocket.

The main problem with mp3 players is the cost of memory, those with a lot of memory are rather expensive. Mine has 32mb built in, and I bought another 64mb at a computer fair, which cost me another £30. (about £55-£60 in shops) You can get some with huge amounts of memory but they are very, very expensive.

It is best to record songs especially to use on the mp3 player, most mp3s are recorded at, at least, 128kbps. This gives about one minute of music per mb of memory. I record stuff onto my computer at 64kbps which effectively doubles the capacity of my player (96mb gives me over 3hrs of music), there is a slight degradation of sound quality at this level, but not bad enough so you'd notice when out running or cycling.

Hope that's been some help

Karl