Also, even though it's correct that Euclid didn't pose it as a proof by contradiction, it can certainly be posed that way, and I often use that form when presenting it to nonmathematicians.

Not everyone thinks the same way. There are certainly lay persons out there who do not find proofs by contradiction jarring when they come across them for the first time. I remember I was one of them.

But the impression I get from my (possibly biased) sample is that most non-trained people intuitively see proof by contradiction (or any form of nonconstructive proof, really) as a way of "cheating", because it asserts something does or does not exist without actually producing a (counter)example. YMMV, of course.