I have bought from Woot two Sansa Views (2GB and 4GB), a Sansa Clip (4GB), and two Sansa Fuzes (4GB and 8GB). I haven't had a problem with any of them, except for the View that my girlfriend decided would be better if slammed in a car door.
I've installed Rockbox on them all: v1/v2 whatever, Rockbox works and it's been incredibly stable.
Linux support is no big deal, since this shows up as a standard mass storage device.
My only recommendation is to dump the earbuds that come with it, as they aren't anything special, and get a set of noise-isolating buds. I personally like the Koss Sparkplugs, which have a terrible build quality (I go through a pair every 2-3 months), but a reasonable price ($12-15) and excellent noise isolation and fit. Unlike other earphones that use rubber, they use foam and that creates a much better seal. With those and the Fuze, I can watch movies on a train or plane without having to blast the volume.
As for encoding videos for this thing (with Rockbox installed), it's a piece of cake on a Linux machine. As long as you have MPlayer (mencoder) installed, then the third post of this thread has the command you need:
As someone who has used a ton of mp3 players, I find these to be the best. I really, really like the physical scroll wheel (as opposed to the touch version on the iPods).