Review of set-with-Set.patch:

Looks good overall. 
I agree that restricting operations to instances of Set rather than Iterable is correct.

Implementing "__rsub__" in terms of - (subtraction) means that infinite recursion is a possibility. It also creates an unnecessary temporary.
Could you just reverse the expression used in __sub__?

Would you add tests for comparisons; Set() == set(), etc.
There are probably tested implicitly in the rest of the test suite, but explicit tests would be good.