"on a mountain high"!
High is kinda the definition of a mountain, no? If it weren't high, it would be a hill.
Also, since my daughter is learning to drive, the phrase "bring the vehicle to a full and complete stop" comes to mind. I've yet to see a full stop that wasn't complete, or vice versa.
My church choir director is forever inviting the congregation to "join together" in singing hymn number such-and-such. A minor annoyance, but it really sets my teeth on edge after the fourth or fifth time I've heard it in an hour.
[Edited to add: This is the opposite of a redundancy, but a few days ago I had to look up the definition of "perspicuous," and felt betrayed. Definitely a case of false advertising.]