Tallest structre using paper and tape works well.
The marshmallow spaghetti towers are often a hit. There is also a neat video about them.
http://www.ted.com/talks/tom_wujec_build_a_tower.html
This video would be fun to watch after the challenge, plus it re-inforces a JVN approved principle (iteration is important).