I really do think the incompleteness theorems deserve the attention they get, not just because of what they say about efforts to formalize mathematics and because of the historical context -- remember Gödel numbers came (just) before Turing and the first recognizably modern electronic computers. That numbers can represent things that are not numbers was (IMO) a revolutionary idea.

Having said all that, I'd taken mathematical logic in college to learn about incompletenss, but the most interesting things I got out of it were completeness and compactness. Non-standard models really can be quite interesting.