The impossibility of tiling a chessboard with two opposite corners removed using dominos is quite good for this purpose I think, especially if you start by giving a boring case-analysis proof for a 4-by-4 board.
The bridges of Königsberg is also pretty good. Marcus du Sautoy spoke about it last night in his series A Brief History of Mathematics on Radio 4 (though he overdid it when he claimed that the solution had "revolutionized the internet").
