I took Larry's request a slightly different way: he has a use case where he wants order preservation (so built in sets aren't good), but combined with low cost duplicate identification and elimination and removal of arbitrary elements (so lists and collections.deque aren't good). Organising a work queue that way seems common enough to me to be worthy of a stdlib solution that doesn't force you to either separate a "job id" from the "job" object in an ordered dict, or else use an ordered dict with "None" values.
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.
The widely used third-party `sortedcollections` module maintains either "natural" order or some key order. That could be engineered to be insertion order fairly easily. Admittedly, 'OrderedSet' sounds a bit different from 'SortedSet'.
In [8]: sortedcontainers.SortedSet(['Wake Up', 'Drink Coffee', 'Make Breakfast'])
Out[8]: SortedSet(['Drink Coffee', 'Make Breakfast', 'Wake Up'])
In [9]: sortedcontainers.SortedSet(['Wake Up', 'Drink Coffee', 'Make Breakfast'], key=lambda s: s[-1])
Out[9]: SortedSet(['Drink Coffee', 'Wake Up', 'Make Breakfast'], key=<function <lambda> at 0x7f68f5985400>)
In [10]: 'Make Breakfast' in tasks
Out[10]: True