One option is to force all categories to be comparable, such as with using pairs (order, value). Another possible solution is not to implement cdf for general RVs, and then there's a possibility to implement a mid-class that is "not-so-general" whose values have to be comparable, and in fact, have to be linearly-ordered.
I believe that I like the most the last idea.