I can only really tell you about the iPod as it's the only one I've used, but from what you've written it might not be quite what you're looking for
Cons:
- Out of the box it requires iTunes to use, and you have to keep a copy of your library on your computer as well. There are programs to get around this but I haven't used them so I don't know how well they work. Also iTunes doesn't work with linux of course. It is pretty easy to use, until your library gets bigger than your iPod, then it's a real pain to take albums on and off.
- The iPod's filesystem is completely whack - it's not really possible to browse the files themselves - the interface works on an ID3 database
- Battery life is OK to start with, but it degrades pretty quickly, especially if you leave it lying around somewhere hot or cold. Mine is down to about 6-7 hours after a year. You can probably replace it yourself, but they're still pretty expensive
- No ogg support, no wma support, no line-in
- From what I hear, sound quality is not so good when compared with some other players - I don't really notice because I can't afford to replace Apple's shitty earbud things.
Maybes:
- You can make your own playlists via iTunes, but I'm pretty sure they're not m3u. You can make playlists on the go
Pros:
- Can easily be used as a USB hard-drive
- Has nice big buttons that are easy to push
- Video playback
It looks like iPodlinux could be pretty useful, but it's only supported up to 3rd gen at the moment - the video will be 6th gen
Also, I'd recommend getting as big a hard-drive as your budget will allow. When I got mine I thought that 20GB was heaps, but when they say 20GB they actually mean 20 billion bytes so the "real" capacity is more like 18.5. Then you need at least another 3GB for it to actually be useful as a hard-drive so already you're down to about 75% capacity for actual music. This might not be a big deal for you but like I say, I didn't think it was a big deal for me either and now it's kind of a major problem