The Halting Problem. The first time I saw this was my senior year in high school and it completely blew me away. All you need is a notion of what an algorithm is and very basic logic (enough to recognize that assuming $A$ and deriving $\neg A$ is a contradiction)
The first beautiful proof I saw in high school (it was beautiful at the time, but now seems too trivial) was the fact that for a geometric series $a, ax, ax^2, \dots$ the sum of the first $n$ terms is $a \cdot \frac{1-x^n}{1-x}$. I thought this was cool because of all the cancellation that seems to come out of nowhere. The treatment here is nice.