I'm not sure that should even be a goal - uniform iteration seems to be saying that we want a single protocol or syntax to represent both the multi-pass sequence (the Array) and the single-pass stream, so the problem is locked-in to the question. One is a mutating operation and the other is not, so it's unclear to me why they should look the same. That mutability carries important semantic connotations - namely, about whether or not iteration change any state (and therefore may not be able to be repeated).
Iterators are definitely single-pass - once they return a nil, that's it, all they will ever return is nil. Sequence claims to be single-pass, but supports creating an iterator without mutating (which somehow is not the same as non-mutating iteration...? 
) - oh, and since almost all real-world Sequences are multi-pass, almost no 3rd-party code gets tested against single-pass sequences, so following that particular piece of documentation is unlikely to be a good idea. If you're actually writing a single-pass sequence, you should expose an Iterator.
It seems to me that changing Sequence to be multi-pass is the simplest way to fix our collection hierarchy (even just to accept reality). Then we can talk about whether Sequence (a multi-pass sequence without a notion of position) makes sense as an abstraction level between IteratorProtocol and Collection (I guess probably not).
I'm not sure how move semantics would help with this - except perhaps as a general variable "poisoning" tool, so we can say "don't iterate this variable more than once" in the same way we say "don't use this variable after its contents have moved out". But for a single-pass sequence, I don't think either the elements or sequence itself need to be move-only IIUC.