My personal opinion, start with a cheap set of Nashbar/performace/etc MTB SPD style pedals, and once you've gotten the hang of them, you can decide to stick with them or switch to Road pedals.

I did this by accident, sort of. The SPD pedals are a little easier to clip in and out of than the road specific SPD-SL pedals. I found they were a good pedal system to learn on. For me, they started causing some pressure issues and I switched to the SPD-SL and am glad I did. I am, however, very glad I started on the SPD system first. Probably saved me a fall or two.