Since the Arduino boots with all outputs open circuit, you need to find what is pulling your relay board input low on reboot and fix that. Of course, it would make it obvious to us what the problem is if you actually revealed what the relay module is, and how you have it all connected (and I mean as always, all of the connections).
Pull-ups are clearly not going to help. I strongly suspect that that you actually mean, is that the relay board is actuated when you turn off the Arduino but leave the relay board powered, since with the power off, the protective diodes will pull the outputs down to whatever the Vcc line is, which is zero if there is no power in the Arduino board.
if your relay board includes an opto-isolator - as I presume it does since almost all of those which take active-low inputs do, then you need to separate the link connecting "Vcc" to "JD-VCC" and power the Vcc from your Arduino whilst you continue to power JD-VCC from the relay supply.