I wrote the response to the OP's use case before I saw your response; it wasn't really intended as an additional critique of the proposed change or a counterargument to your post, just a note that the required behavior could be obtained on all versions of Python via metaclasses, including on 3.5.

I have no specific plans to rewrite the typeobject.c, nor make a C implemented WeakSet. I'm just leery of adding language guarantees that limit future development when they:

1. Provide very little benefit (I doubt one package in 10,000 even uses __subclasses__, let alone relies on its ordering)

2. The benefit is achievable without herculean efforts with existing tools (metaclasses can provide the desired behavior with minimal effort at the trivial cost of an additional side-band dict on the root class)

If the guarantee never limits a proposed change, then our best case scenario is we provided a guarantee that benefits almost no one (guaranteed upside minimal). But if it limits a proposed change, we might lose out on a significant improvement in performance, code maintainability, what have you (much larger potential downside). I'm just not seeing enough of a benefit to justify the potential cost.