Really excited you got the Specialized bike, looking forward to hearing lots of great progress on that monster.
I bought Pearl Izumi X Road, now $33 (plus shipping) in limited sizes from where I got it:
http://www.jensonusa.com/Pearl-Izumi-X-Road-Shoes SPD pedals, you can walk in them after cycling, I would commute in them, then use them for work, nobody ever asked why I was wearing cycling shoes at work.
However, I would recommend two things. Firstly, buy a cheap shoe in the brand that you can move forward with and trust the sizing of. I'd recommend the 3 S's, Shimano, Specialized, Sidi, however, with wide feet, make sure you only choose the wide option of Shimano or Sidi, not sure what to do with Specialized, if they aren't wide enough not an option. I've heard Northwave are decently wide too, so the previous suggestion about Northwave might also be good. The main thing about this is to get sized up locally in some cheap shoes. $65 online might be $95 in a LBS in Aus, and you get to try them on, but that might be $200 online vs $300 when you go to upgrade in a year or so time, and you'll know and love the sizing of your previous cheap shoes, so you can spend the money online with more confidence later. Use bikeexchange again for the local bargain, or google a shoe you have your eye on, and try the shoes on. When you find the right size, sit in them for 15 minutes in store. They should feel tight around the heel every time you try to lift it, but not tight on the toes, or around your wide feet. Up and down is the main issue here. The main point here is comfort is king when it comes to riding a bike, and you need to start locally, find a comfortable brand sizing, then you can buy more expensive shoes online in that brand later if you need to.
Second part is road vs MTB cleats. I recently switched from cheap SPD (MTB) to expensive SPD-SL (road), so can say the difference between clip in and clip out is next to nothing, and cheap vs expensive shoes is fairly subtle performance wise, mainly about comfort from what I can tell. I would recommend road shoes, as they are made for what you are doing. This changes if you intend to walk a lot in them, but if your main intention is to ride, I don't see why you'd need MTB shoes. I started with SPD, but then had to change my pedals, cleats and brand to upgrade properly, so I firstly felt like I needed to do the upgrade to get closer to my end goal, and then needed to change a lot of gear too.
If you choose road, you can get the sweet spot of pedals right now, the Shimano 105, $45 from
Wiggle. From what I've read, you won't get much more out of more expesive pedals, so could aim to keep these even after a shoe upgrade later on. They can be adjusted to be tight or loose, meaning you can get used to clipping in while really loose, making it much better for the beginner and tighten it later once you get comfortable. The pedals also come with the standard SPD-SL cleats (as would SPD cleats with SPD pedals), so once you buy a cheap pair of shoes and 105 pedals, you are set to go. Perhaps order a pedal wrench while you are at it on
wiggle, it might come in handy later as well as the initial change over.
Good luck.