Kristin Looney likes to demo Zendo, and so do I. The rules are short, and when you start with simple rules there are quick iterative rewards: wiki.playagaingames.com/tiki-index.php?page=Demoing+Zendo
I'm partial to demoing Pikemen, myself. Easy rules, interesting strategies and situations. Two player is best, especially for tournaments. Single-elimination.
I think that IceTowers is also great for demoing because it has few rules and is completely different from Zendo and Pikemen. I don't find the problems you mention with IceTowers, because there is actually an incentive to play a little slower, but not too slow. It's a tricky balance, and I think Andy did a good job of creating a real-time game that does not reward the fast nor does in encourage you to wait forever.
After people play all three of those games, they see how versatile the pieces are.
-Jacob