As far as pedals... I personally would recommend starting out with a multi effects pedal. I was torn by the same indecision, but ended up purchasing a Digitech RP250 and do not regret it. IMO, for a relatively small investment, it (or any multi effects pedal) gives you a chance to try a variety of effects and decide which ones you like/need the most.
You can then continue to use it to to sit in for other effects that you haven't purchased yet.
...so ever since then, I always hang on to the buckle.