I have issues with type classes as well but I share this concern with Brian - by parameterizing the entire data structure on a dictionary every method has that constraint, even those that don't need it (e.g. empty).
I still don't understand why its the end of the world. It's needed because the way you order the set is important for the semantics of the data structure. I'd be fine with the tradeoff.
From a different perspective, leaving off the 'Ord' from empty could be seen more as exploiting the hack that type classes build into the language - ie. global coherence. Not saying I necessarily agree - but I don't see it as clear cut.🤷♂️