Sets are not used only as mathematical entities.  Preserving annotations is potentially important.  In particular, instead of implementing union in terms of ++, one might expect to implement ++ in terms of union.  Although in general I don't support preserving weird undocumented behavior, having either consistent left-preference or right-preference is pretty common.  I worry about introducing bugs if this changes dramatically.

In many cases structural sharing should obviate the need to slow things down any more anyway.  You already have to check if they're equal.  Adding an eq check won't cost much.  (Granted, it will double the logic in some sections.)

Is there time to make such a change or is it too large to do robustly at this point?