Yah, I like both of them a lot, but I find them hard to explain to those who aren't already in some sense "into math." I was going to include Euler's equation, but left it out for that reason. I do sometimes explain 3-coloring of graphs, and can sometimes get to NP-Completeness, although it's a bit of an effort.

However, I don't want to preclude stuff that maybe can be explained, even if at first glance it doesn't seem so.

Maybe you should actually state Cook's theorem. :-) (It states that k-SAT is NP-complete, btw.)

Why is it important? It was the first result that identified a naturally-occurring, NP-complete problem. Thanks to Cook's theorem, to prove that problem X is NP-complete, we can always use the strategy of providing a polynomial-time reduction from k-SAT to problem X.