You'll probably end up with both in the end. If your amp has an FX loop I'd suggest some sort of multi-unit in the loop. Use this for all you time based FX; Delay, Verb, Chorus, Tremelo, Phase, etc. You'll generally want to avoid FX that change the envelope (tone) of your signal in the loop (with the possible exception of EQ). These include Distortion Units, Wahs, and Envelope Filters (auto-wah). These are generally best in front of your preamp/amp in order to change the sound of your signal before the pre-amp puts it's sonic stamp on it. Compressors can go just about anywhere, and will affect the sound differently depending on where you put them. Same is generally true of EQ.
You may want to decide on how you want to affect your sound first. What's missing from your current setup? If you just a few things, like distortion and delay, go with pedals. If you want lots of different sounds available, the programmability of a multi unit may make sense. One advantage that newer multi units have is the ability to change the routing of the effect. This control is nice to have and if you like to sit and tweak, can enable some really weird stuff...
You also want to think about how the unit will work w/ your amp. What kind of amp do you have? Like the sound you get already? Have an FX loop? etc.
As far as favorite pedals/FX go:
Boss DS-1 (anyone in the forum NOT have one?)
Morley Bad
Horsie Wah
Ibanez PC-10 Prime Dual Chorus
Boss VF-1 (can replace the preamp if yours isn't super)
TC G-Force
Roland DEP-5 (lusted after this until I found one used in '88. Mid '80s rack delay/verb/chorus. Classic Roland. Go for $100-$160 on ****)
Pedals I've had that I don't really use much
DOD Envelope filter
Korg Octave Pedal
You may want to find a shop w/ a patient sales person and good selection of gear. Take your guitar in on a weekday afternoon when nobody's there and play everything you can get your hands on.
FWIW,
-bill