The thing you'll want to look out for is hard, stff, soles, yes. I bought a pair of biking shoes (for outside) that were really spinning shoes, and they were really only sneakers with cleats built in. Not good for riding outside, and I don't think even really good for spinning. I still use them for spinning, but will eventually replace them.
Just make sure that your cleats match the type of system on your spin bike. I think most (all?) spin bikes have SPD cleats?
If you have wide feet, you may want to check out Specialized. Most cycling shoes seem to run narrow.