My personal favourite, among the canonical "first proof" proofs, is the proof that every number has a prime factor (and, as a consequence, that there are infinitely many primes). Honestly, everyone's heard of the Pythagorean theorem, and a proof won't really "expand many people's horizons" as far as mathematics goes. I like introducing people to the prime number proof because most people have no conceptualization about how you would go about proving something about every whole number in existence, so the proof offers a taste of mathematics that they've probably never even imagined before.
Alternately, instead of giving a rigorous proof, you could take a discipline like abstract algebra and give a conceptual understanding of the "algebraic" approach to tackling a problem (i.e. stripping away extraneous detail and focusing on the barest structure of the thing). A very good example would be bracelet counting with Burnside's theorem. You could talk about how the whole problem basically reduces to finding collections of bracelets that can be obtained from each other by rotations and reflections (i.e. the orbits generated by the action of the dihedral group on the set of bracelets). Or, you could talk about how things like addition and multiplication in the reals can be considered as binary operations, and that once you see it that way you see all sorts of similarities between things like the integers, permutations, and symmetries of geometric figures (i.e. the group structure).
