If you had not mentioned the noise from the O2 sensor relay with the key out of the ignition, I would suspect the crank position sensor. They tend to fail intermittently, so the problem would likely recur if that were it.
If the electrical glitch with relay is related, then I don't know where to begin other than down the long step-by-step electrical diagnostic trees in the service manuals. Not fun to do, and not particularly helpful if it decides to work properly while you are checking it.