Someone correct me if I am wrong here, but the Arduino output does not go low when it reboots, it is open circuit and will not actuate the opto-coupler.
No correction required here. Pins default to inputs and so can and will float so there is no current path and the relay will not turn on.
Oh, and if the relay power supply is only used for the relay board, do not deliberately connect its ground to the Arduino ground.
I would disagree with that. You need to sing the current to activate the opto to activate the relay so you do need the arduino ground connecting to the relay board ground if it has a separate supply.
Arduino Vcc should never be used for powering motors, relays, or other than a couple of LEDs drawing 10 mA or so.
I would disagree with that as well, providing you apply sufficient decoupling you can run everything off one supply. If you don't decouple then the simple way round is to use a separate supply.