The fact that suffix trees/suffix arrays can be built in O(n) is IMO the most surprising and "magical" result in computer science. To me, more surprising than median of medians/quick select.
There might be more "magical"/surprising things that are obscure and I am unaware of, but to me, this is it. :)
The Alias Table for sampling a discrete distribution in O(1) time is a very clever idea https://www.keithschwarz.com/darts-dice-coins/