Just a practical advice. I would not let the camera focus for each shot because one lens may hunt for focus longer than the other and you most likely won't get simultaneous shots.
Set the focus to manual and you need to trigger only the shutter.
I'm also not too sure about connecting the shutter pins together. I'd avoid it, if for no other reason, than just to keep my mind at ease.
An optocoupler such as 4n35 is sufficient replacement for your relays. My guess is they are cheaper and less bulky, not to mention silent. They can also be driven by the Arduino board so you don't need 9V (battery ground should be connected to Arduino ground).