Anything by Clutch, Floor, and Desert Sessions. Clutch has matured in their sound but always put out a quality product. I would start with Pure Rock Fury and if you like that then you will like both their later stuff and their earlier stuff.
Check out Floor at Stonerrock.com, I dug their samples enough to order all of their albums. Same thing with Mondo Generator. I will review them in my Recent Purchases thread when they get here.
Desert Sessions are an odd bird. Some songs showcase Homme's/Oliveri's typical sounds, but others are different from anything else they have done. I Want to Make It With Chu features PJ Harvey on backup vocals and a good indication of some of the stuff on these records (granted I have only heard Sessions 1-4, I believe). You can check out a live video of this track in the Multimedia portion of the QOTSA website. Pretty killer if you ask me.
There are some clips of the Eagles of Death Metal on the QOTSA site as well, I didn't like them. Cheesy, faux 70's sound with no bass.
I recently bought Start The Machine by Fu Manchu and damn near every song sounded the same to me. Also, the singer has a weird voice which I really don't dig. I was kinda bored with it, I can send it to you if you want.