Sometimes, when mowing the lawn, it can take me up to 4 hours so I have to take that into consideration for disk space and battery life.

Ooo, tough one.

Is it critical that it be able to play 4 hours' worth of songs without repeating itself? What about the relative quality of the files?

If you want both high quality and not-hear-the-same-tune-twice capacity, then you are talking about hard disk based players right now. Current leaders are of course the Apple iPod and the Rio Riot. The iPod is physically very small, but if you can handle the slightly larger size of the Riot (for instance clipped on the back of your belt), I'd definitely choose it over the iPod for lots of reasons (one of which is greater capacity than the iPod).

If you don't mind converting the tunes down to 96kbps for the portable player, and don't mind repeating tunes once or twice, then there are lots of solid-state portables that fit the bill. Of course, then there's the time-sink issue of transcoding all of your high-bitrate-empeg-MP3s to the lower bitrate to fit on the portable... the hard-drive portables start to look even more attractive...

Ah, if only there were a solid-state portable made by the Cambridge team... OH WELL.

Regarding headphones: Most portables I've seen will ship with abysmal headphones. Expect to use another pair other than the ones that ship with the player. For mowing the lawn, I would recommend these. I have used them with portables while working with loud power tools out in the garage, and they effectively work as earplugs as well as producing excellent bass response.