To suggest radical overhaul of the established protocol hierarchy, it's not good enough to just say "this must be a problem". There needs to be clear evidence that it is a problem. We need to see that it's a likely that someone might, say, write a generally useful algorithm on Sequence using a method such as starts(with:), then have a reasonable expectation that algorithm would work with a Set yet get surprising results that could be considered "incorrect" given Set is unordered.
So far the only compelling example that has been found is the one of Set.elementsEqual – hence the proposal to rename it. Other than that single case of possible misnaming, I've seen no such evidence that there is an active problem being caused for Swift users. Pointing to conflicting definitions in other languages or fields is not enough. It might have been enough when the protocols were being designed and named originally, or even shortly after they were widely adopted, but not in Swift's fourth (nearly fifth) year. Even then, the alternative would have to be better: and a more technically correct but also more complex solution would not be. We learned this lesson with String's Collection non-conformance.
Note that the properties first and last are on Collection not Sequence. They are defined as self[startIndex] and self[index(before: endIndex)] respectively (note the latter needs the collection to be bidirectional, which Set is not). There are many useful algorithms that can be built on top of the ability to pull elements off a set in the same order over multiple passes, as you can with any collection.
Extracting these properties out and putting them on a different protocol, as Brent pointed out at the start, implies not just a separation of Sequence and some other protocol – but a creation of an entire parallel set of protocols alongside the existing collection hierarchy. This dramatic increase in complexity would need to be justified – which again leads us back to the need for specific, concrete, compelling examples to justify that complexity. And when I say compelling, they need to be very compelling to justify extensive, source-breaking overhaul this would require (far more than the simple single-method rename proposed by SE-0203).
This is not to say that the protocols are perfect, or not in need of further debate. The single/multi-pass nature of Sequence, and the way that SubSequence works, is still a topic worthy of exploration and potential change (so long as that change can be made in a source-(and soon ABI)-stable way). But revisiting naming based on theoretical concerns, or totally overhauling the hierarchy in a way that would increase complexity with little upside, is not useful and at this point should be considered a settled discussion.