I think it's also worth noting that requiring an ordering is preventing a performance optimization

This doesn't impact most high level python code, and an OrderedDict is a very reasonable default. But there's a reason why Google's c++ map intentionally randomizes iteration order

(Hint: it allows the hash map and hash function to be extremely high performance while allowing themselves the flexibility to change the hash function)