I'm not going to stay heavily invested in this, but I think if you want to weaken Equatable to something O(1), it's worth it being a tri-state. Two ASCII strings of unequal length are "definitely unequal"; two strings with the same backing storage are "definitely equal"; two strings with the same length and different storage we can't say anything about.
(I'm not actually saying we should or shouldn't implement this for strings, it was just a convenient example.)