I think a little bit of mathematical logic should be included. Not-too-technical descriptions of what formalized proofs are, what models are, Tarski's definition of truth, Gödel's incompleteness theorem, the halting problem for Turing machines. Also Cantor's diagonal proof that the reals are uncountable, and maybe some historical info about how the religious community reacted to that theorem (apparently they reacted badly, see the wikipedia biography of Cantor).

Chaos and the butterfly effect deserve a mention.

A few examples from computational complexity theory could be cool. Scott Aaronson has some nice ones here.

I once explained public-key cryptography to a music major (showing how RSA worked) and I think he understood it and appreciated it.