[David Mertz email@example.com]
It's not obvious to me that insertion order is even the most obvious or most commonly relevant sort order. I'm sure it is for Larry's program, but often a work queue might want some other order. Very often queues might instead, for example, have a priority number assigned to them.
Indeed, and it makes me more cautious that claims for the _usefulness_ (rather than just consistency) of an ordered set are missing an XY problem. The only "natural" value of insertion-order ordering for a dynamic ordered set is that it supports FIFO queues. Well, that's one thing that a deque already excels at, but much more obviously, flexibly, and space- and time- efficiently.
For dicts the motivating use cases were much more "static", like preserving textual order of keyword argument specifications, and avoiding gratuitous changing of order when round-tripping key-value encodings like much of JSON.
So what problem(s) would a dynamic ordered set really be aiming at? I don't know. Consistency & predictability I understand and appreciate, but little beyond that. Even FIFO ordering is somewhat a PITA, since `next(iter(set))` is an overly elaborate way to need to spell "get the first" if a FIFO queue _is_ a prime dynamic use case. And there's no efficient way at all to access the other end (although I suppose set.pop() would - like dict.popitem() - change to give a _destructive_ way to get at "the other end").