Yeah, I understand why so many languages try to do immutability this way. Because it doesn’t require a new language concept, just an addition to the stdlib.
But the types being incompatible is quite a problem.

The most meticulous solution that I’ve seen for this, is in Scala. This is the diagram of immutable collection types:

…and these are the mutable collection types:

The blue blobs are traits/interfaces, which are shared between the two, so that mutable/immutable (as well as conceptually similar) types can all be accepted into the same API.

And they’ve got this system, where you can construct a trait and it’ll actually return a value of a concrete implementation. (Bold arrows in the diagram.)

So, in practice, this is actually pretty elegant. If you want to accept a list as a parameter, you specify the Seq trait as type constraint.
And if your users don’t care about what type of list it is, they can construct a Seq to implicitly get a List, which will fit into the Seq type constraint again. 🙃

But yeah, the complexity under the hood is quite something. Obviously, there’s more to it than immutable vs. mutable, but making that a language concept instead would certainly help to reduce the complexity…

Diagrams from here: https://docs.scala-lang.org/scala3/book/collections-classes.html#collections-hierarchy