If you decide to get Specialized shoes just go a size bigger than you normally wear and they should be fine. I have some of the Body Geometry SPD ones and had them for two years and they are still nearly as good as new. Great shoes, really comfortable.
I love to be clipped in and having Shimano multi release cleats (SM-SH56) I have never felt like I could unclip in an emergency.
It's hard to tell if they make a huge difference to efficiency. But when I have used regular pedals recently my feet just appear to be sliding around all over the pedals. Something I was unaware of happening until I went clipless.