"He had left the house when we arrived." I feel it is most certainly wrong, but I figured it's safer to ask the community here. To me it feels like it should be "He had already left the house when we arrived," or "He had already left the house by the time we arrived." Am I wrong here?
Both of the alternatives you offer are grammatically correct and idiomatic, but the first supplies additional meaning to what was an already grammatically acceptable sentence.
Already simply adds emphasis to the fact that he had gone, hinting that the speaker or their interlocutor would have expected him still to be there.
By the time is simply an alternative to when.