Cycling Shoes/Pedals and advice

The pedals generally come down to personal preference.  I have used Look pedals (classic and the newer Keos) and like them.  Many like Speedplays.  There are others as well (e.g., Time, SPD).  Each has a slightly different interface between the shoe cleat and the pedal.  Any will work well and make you more efficient when you pedal--many see ~1mph just from going clipless.

As for shoes, I would try to get these from an LBS so you can try them on.  Fit is really the biggest issue.  And the benefit of having comfortable feet while riding can't be overestimated in my view--especially if you are looking to "ride lots".  You can get good deals on-line but, unless you know the shoe works for your foot, it's hard to know if a deal is really good for you in advance.  If you buy pedals and shoes together, the LBS will also probably help you fit the cleats to the shoes as part of the deal (or maybe charge a small fee) which is also very important since your feet will now be "locked" into one position.

You can practice in a trainer, if you have one, to get the feel for the pedals.  Otherwise, start in a parking lot or neighborhood street and practice as you stop & start.  Inevitably, you will "join the club" and topple over as you forget to unclip when you stop.  Hopefully nothing will be hurt but your pride. 

I have Look, Look Keo Classics, and SPDs on my bikes. All are fine as are a lot of others. I think pedals are way overrated.

As for speed, don't look for any big improvement. Maybe 1/2 mph?

As for clipping in / unclipping: There are two types of cyclists; those who have fallen and those who will. It will happen but you learn from it.

As for shoes, buy them from an LBS because every manufacturer has a different interpretation of sizes. I wear a 45 in Shimano but a 44 in other brands.

Are you gonna go with tri or road shoes? Ratcheting road shoes fit better as you can really adjust them precisely, but are inefficient for tris. Tri shoes have one or two straps but don't fit as precisely.

Really good advise overall.  I've used Looks and SPD's on my road bike (and SPD's and eggbeaters on my mtn bike).  Look makes a cleat with a little bit of rubber on it that helps counteract the ice-skating feeling you will otherwise get from road shoes, which is why I use Looks when I am racing.  If I am touring around, I'll use SPD's with a light duty mountain bike shoe, that I can walk normally in.  But they are kind of heavy and takes a little longer to get in (even though I have Yankz on them) than my tri shoes.