Proofs that expose a deeper structure
I'm not sure this is quite what you're looking for, since I've seen the "uncommon" proof in textbooks, but: the O(n log n) time bound for quicksort.


"Textbook" proof: set up a randomized recurrence relation, prove by induction that it has the desired solution.
"Uncommon" proof: find a simple formula for the probability that any two elements are compared (it's just 2/(d+1) where d is the difference between their ranks in the sorted order), and use linearity of expectation and harmonic series to compute the expected number of pairs that get compared.


The textbook proof requires less creative insight, but the uncommon proof introduces a technique that's very useful in other algorithm analysis e.g. for randomized incremental algorithms in computational geometry.