I notice no one mentions Godel's Incompleteness Theorems, or the basic non-computability results of Turing.  Are they too obvious?

If these are not constructive enough, one that is fairly elementary is a space-filling curve.  If you want something non-intuitive, how do you like a continuous surjection from a 1-dimensional space to a 2-dimensional space?