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?