Teach them something surprising, something memorable. 

Looking through the contents of "The Heart of Mathematics: An Invitation to Effective Thinking" by Edward B. Burger and Michael Starbird, among other things they talk about number theory (up to RSA encryption), irrational numbers, different sizes of infinity, the fourth dimension, knot theory, fractals, and counterintuitive probability.

These are all the kinds of things that excite mathematicians, and we should try to give our students some sense of that kind of excitement. Burger and Starbird's book is designed for a ``liberal arts'' type course, and I think they demonstrate that it's possible to give an understanding of what's going on in a way that is at least somewhat palatable to non-mathematicians.