The only major design decision is (I think) whether to store the elements in a linked list or dynamic vector.
My personal preference is to specify the ordered set via a flag to the constructor, which can be intercepted by __new__ to return a different object type as necessary.
(If anyone wants to add a complete ordered set to PyPI that would also be very useful for me!)