Another example that just came to my mind is the "set of all sets that do not contain themselves" in Russell's paradox - it was very simple, as unexpected as anything and turned the ideas about sets completely topsy-turvy.