After a while I agree with @CTMacUser about generalizing for Collection. After all it isn't the consumer's problem that the Standard Library has this so far small issue with useless methods for some sequences. We must respect all collections, and besides, contributing to the aforementioned issue isn't a bad thing to do either.
But as you say, then comes the question of whether to further generalize for Sequence. First of all, it is worth mentioning both methods, even in their most optimized state, require the ability to non-destructively traverse a sequence multiple times. I wouldn't be punishing single-pass sequences in this case, since the methods wouldn't work at all. Though we might be punishing infinite sequences and other sequences that aren't collections.
Also, we must not forget that Sequence is a top-level abstraction and must contain minimum functionality to appropriately generalize and carry it's role. Loading Sequence with extended functionality or setting a precedent isn't desirable.
By the way, the illusive similarity of contains and isSubset might become a typical misusage case.