which means that even within the same process, calling keys() twice on the same hash will result in a different key order.
That's not what it means at all. For a given hash, multiple calls to keys (and values) are still guaranteed to return the same order if there has been no change to the hash, and the order has always been subject to change after hash modifications.
Difference one: The order is more likely to change on hash modification.
Difference two: In a given interpreter, if you built two hashes using identical insert and delete steps, you used to get the same key orderings. This is not always the case now.