Hundreds of people want an orderedset (http://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set) and yet the ordered sets that are in PyPI (oset, ordered-set) are incomplete. Please consider adding an ordered set that has *all* of the same functionality as set.
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!)