Cantor's Diagonal Argument: http://en.wikipedia.org/wiki/Cantors_diagonal_argument It's simple and it reveals the surprising result that, to put it crudely, 'some infinities are bigger than others'.

I don't know about beauty, but I realized I was done with math during my functions of a real variable class when we did a proof to the extent of, "There exists a rational number between any two irrational numbers. There exists an irrational number between any two rational numbers. Prove that their are more irrational numbers then rational numbers." Re countably infinite versus uncountably infinite.

Thankfully my crypto course came along a few years later and restored my faith in math.

It's more physics than pure maths, but artist & art critic Matthew Collings made a documentary for the BBC called "Beautiful Equations". More info here:

http://www.bbc.co.uk/programmes/b00wltbm

Worrydream.com has a few great examples of displaying complex information intuitively.

I think there's a lot of beauty in the fact that e(i*pi) + 1 =0

while at university I witnessed a fellow student loose his faith from a lecture on fractals.