L'impostazione dei pin HIGH prima di dichiararli come output (attiva INPUT_PULLUP) o l'utilizzo di pullup esterni funziona correttamente, ma avrai un problema allo spegnimento come dici tu.
In un'impostazione ho due diversi alimentatori 5V, uno per Arduino, uno per i relè. I GND sono uniti e i pullup sono collegati all'alimentazione 5V dei relè, non all'Arduino. In questo modo quando spegni Arduino i relè sono ancora alimentati e vedono un ingresso HIGH.