First off, the OP's original case seems like a use case for functools.singledispatch. Not really related to the problem, just thought I'd mention it.

Secondly, are we sure we want to make such a guarantee? That restricts the underlying storage to ordered types (list/dict; possibly tuple at the cost of making modifications slightly more expensive), or an unordered type with additional ordering layered on it (like old-school OrderedDict).

That does tie our hands in the future. For example, it seems like it would be a perfectly reasonable approach for the internal collection of subclasses to be implemented as a weakref.WeakSet (some future version of it implemented in C, rather than the current Python layer version) so as to reduce code duplication and improve handling when a subclass disappears. Right now, tp_subclasses is a dict keyed by the raw memory address of the subclass (understandable, but eww), with a value of a weakref to the subclass itself. There is tons of custom code involved in handling this (e.g. the dict only self-cleans because the dealloc for classes explicitly removes the subclass from the parent classes, but every use of the dict still has to assume weakrefs have gone dead anyway, because of reentrancy issues; these are solved problems in WeakSet which hides all the complexity from the user). Being able to use WeakSets would mean a huge amount of special purpose code in typeobject.c could go away, but guaranteeing ordering would make that more difficult (it would require providing an ordering guarantee for WeakSet, which, being built on set, would likely require ordering guarantees for sets in general, or changing WeakSet to be built on dicts).

There is also (at least) one edge case that would need to be fixed (based on a brief skim of the code). type_set_bases (which handles assignment to __bases__ AFAICT, admittedly a niche use case) simplified its own implementation by making the process of changing __bases__ be to remove itself as a subclass of all of its original bases, then add itself as a subclass of the new bases. This is done even if there are overlaps in the bases, and even if the new bases are the same.

Minimal repro:

    >>> class A: pass
    >>> class B(A): pass
    >>> class C(A): pass
    >>> A.__subclasses__()  # Appear in definition order
    [__main__.B, __main__.C]

    >>> B.__bases__ = B.__bases__    # Should be no-op...
    >>> A.__subclasses__()           # But oops, order changed
    [__main__.C, __main__.B]

I'm not going to claim this is common or useful (I've done something like this exactly once, interactively, while making an OrderedCounter from OrderedDict and Counter back before dicts were ordered; I got the inheritance order wrong and reversed it after the fact), but making the guarantee would be more than just stating it; we'd either have to complicate the code to back it up, or qualify the guarantee with some weird, possibly CPython-specific details.