I just filed https://github.com/rust-lang/rust/issues/84346 to account for some cases brought up and I completely agree with your last sentence. It is something that others and I have been doing piecemeal for a while now and would encourage you (and anyone else reading this) to file tickets for things like these at https://github.com/rust-lang/rust/issues/
In some of the cases in this discussion, isn't the problem the compiler has to solve a little bit simpler? From (a) the indeterminate type of the result and (b) the invocation of a method on that value within the same scope, we should be able to infer the trait that the user is relying on. (Assuming the trait itself is in scope, which, if it isn't, is already an error that hunts for appropriate traits to suggest, I think?)
In some other cases we've discussed here, the actual trait we want is named in the return type, which also fills the role of (b) above. I think this is the case you outlined.
I guess my point is, it seems like we already have enough local information to avoid doing a type-driven trait search. In one case, we have a method and two non-unifiable types, and in the other, we have a trait and two non-unifiable types. I can see how the more general case of "just two non-unifiable types" would be hard, but I'm not sure we have to solve that to cover a meaningful chunk of the problem space.
Maybe if there's an attempt to invoke a method on the result later, like in this case, the compiler could point to it in a "note" and say "Would not be able to determine statically which `impl` of this method to invoke", or something.
Users with experience in languages like Java and Python will have a reasonable expectation that code like this should work, because "they both implement iteration" [0]. It's definitely not obvious that dynamic dispatch is why that can work, and how Rust's static dispatching default impacts idioms like this.
It's singularly frustrating to try to express yourself in a language where familiar idioms just don't carry anymore -- as anyone who's gone from Haskell to Java can attest. I think it's valuable to recognize the idiom and gently teach users why Rust differs.
[0] https://news.ycombinator.com/item?id=26867490