I'd go ahead and just buy a pair of shoes before you buy new pedals. It's really easy (5-10 minutes of pedaling around?) to get used to clipless. It'll be easier to learn on the double-sided pedals (don't have to worry about flipping pedals over) and you won't have as much money invested if you don't like clipless.

I have clipless SPDs on my Merckx (don't shoot me!) and clips on my Olmo and Rauler. I use Shimano MTB shoes with a low profile/narrow toe box, and can therefore use them with all three bikes.

Mine are no longer made, but they're pretty similar to these...

http://www.cambriabike.com/shopexd.asp?ID=39466