Must-have pedals on a board for me: tuner (Boss TU-2 works great); at least 2 overdrives (Maxon OD-808 for classic-rock crunch, Ibanez Super Metal for heavy distortion); boost (I use a Danelectro "Transparent Overdrive"). I also use Ibanez chorus and flanger, and have been swapping in and out between other pedals like tremolo, analog delay, and treble boost. Didn't used to use a lot of wah, but I do now, and have been enjoying using a parked wah sound on some leads; would like to add a Q-Zone sometime to be able to quickly switch to that sound and have it set without having to hit the wah pedal and then adjust it to the setting I want. My pedalboard is small, though (8 standard pedals max), and given the size of some stages, I want to keep it that way.
For my Maiden tribute band gig, I use a rackmount multi-FX unit - a Pod HD Pro for now, which doubles as a preamp, but down the road I plan on upgrading to the full DM setup (Marshall JMP-1 preamp with TC G-Major or G-Force effects unit).
I tried using a pedalboard, but switching sounds in the middle of a complex Maiden song just wasn't working -- if I had to hit more than one switch (say, boost and wah to go into a lead) I might miss a note or several.
With the Pod HD and foot controller, I can set up banks of 4 patches based on the song (one standard bank for most songs, with basic rhythm patch, 2 lead patches with long and short delay settings, and clean; then other banks with specialty patches like the Powerslave lead tone or a wah lead). Now that I'm getting used to it and getting a little spoiled by all the effect options and quick switching (like being able to program 2 different delay settings, and have each one instantly on tap without having to bend down and twist a knob), I may get another for my cover-band work.