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.
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.