I was a little shocked to learn about the undecidable Post Correspondence Problem. But when phrased about the unrecognizability of the complement, it is a lot less shocking.