> It can't be inconsistent. You've got one copy of the data in memory, everything uses that, everything sees the same thing.
Wrong. For instance, state can be stored in locals. Two threads accessing the same structure, one reading and one writing, the reader loads some state into locals and the writer then invalidates that state in the middle of the reader's computation, and the reader proceeds to computing a result mixing old state and new state thus leading to inconsistency. This ABA problem is well known and it just can't happen if the structure is immutable. And this doesn't even go into cache coherency issues.
I frankly don't think you appreciate the number of hazards just making data structures immutable actually addresses, and given you don't seem aware of the hazards implicit to mutable data structures, I suppose that's not surprising.
> What kind of programs would you write that would benefit from this
Pretty much every single program that accesses a relational database benefits from this. There are a few of those around n in case you didn't know. Perhaps you've heard of multiversion concurrency control?