I started with mountain shoes for ease of walking; the difference for road-specific shoes matters less the less you ride, so early on it's fine.
As a fellow wide-feet cursee, I ride in Lake shoes, which are a PITA to get in this country, but can be done. Sidi also offers wide shoes, at least for mountain. Also, within a given brand, lower-end shoes tend to be wider.
Also, running is awesome.