I enjoy my Sandisk sansa e280. I can watch video in a decently large enough screen (I wont watch a movie on anything smaller than a laptop screen), listen to music with a storage of 8G. It is solid (It slipped out of my hand quite a few time, violently even, never got broken), and it has a nice interface.
Add rockbox on it, and you have everything you need (with a somewhat uglier interface).
I have a Creative Zen Stone, and I'm pretty happy with it. It also has an FM tuner (with surprisingly good reception), a voice recorder, and is only about the size of a iPod Nano (or whatever those really tiny clip-on iPods are). It lacks a clip of any sort, which is unfortunate, and is only 2GB, but it's pretty cheap.
I'm going to have to say an iPod. All my friends who got MP3 players had them fail or die within a year, Everyone with iPods has had them last a very long time. My ipod is reaching its 2.5 year mark and still going fine.