Beyond the distortion, EQ, preamp and speaker/cab itself the missing part in most chains for getting a top notch tone is a combination of noise supression and compression. Pedal combinations are a great way to learn how to get a good tone - easier than tweaking a multi processor but multi processors have every pedal imaginable plus a hell of a lot more although I think they are more suited to recording as most of the fancy effects are done post recording now anyway. The other nice thing about a good processor is you can record direct which cuts out all of the hassle of dealing with mics, changing room variables and the volume it takes to push a speaker/tubes to get a sweet tone (its almost impossible to go back the next day and get the same tone even with the mic and amp setup in exactly the same position).
Anyway, if you can afford it, try to get a good quality noise supressor too - Rocktron also make a Hush pedal but if you can pick up a second hand Super Hush C rack unit then go for it!
Re multi fx units, I've owned a lot, Podxt, Boss GT-Pro, Digitech GNX and a few stomp boxes. I traded them all in at one stage or another and now have the only unit I have ever been 100% satisfied with - Rocktron Prophesy II. They arent cheap but you can get the originla Prophesy handy enough on EBay and just upload the software upgrade to get the artists presets (Rusty Cooley, Dave Mustain etc). Best piece of gear I have ever owned, the only unit that preserves the guitars tone and feels like playing through a real amp when going direct to the board - pretty much all I ever use now.
Let us know how you get on with the pedal search and a review of the end unit would be cool too!