I think removing methods from the Hashmap was not in scope for their work - they were working on the JDK, and presumably didn't have the bandwidth to patch every single Java library used at Google to use set-based methods instead of iteration-based.

Also, I think in practice you'll find you want to extract items from a set in some order, so you need some kind of transformation from set->list. e.g: you want to print them out.

Edit: Forgot to address your main question. If the specification requires a specific ordering, the implementation is forever bound to do that, even if other implementations would be more efficient/secure/other-desirable-properties. By introducing randomness, you reduce the risk of people accidentally relying on unspecified behavior, and are more able to change your implementation later.