I was (and still am) astonished by Kleene's Second Recursion Theorem. On the surface, it seems simple and not very useful but I later found out it's deep both mathematically and philosophically.

When I also read about the variant proven on Turing Machines (very very informally stating that machines can obtain their own descriptions or equivalently that there are machines that output their own description, like a program that prints itself..), I felt my brain twist so hard, yet intrigued like never before. Then, you see how the theorem is used to give one line proofs for undecidability of halting problem and unrecognizability of minimal machines..etc.