One thing you might miss is the ability to do late binding and open recursion
In the absence of objects, that's what `letrec` is for. Scheme, OCaml, and SML all have it. In Haskell `let` is `letrec` by default. Clojure has `letfn`. C has forward declarations. Without these features you wouldn't be able to write mutually recursive functions.
You can emulate late binding in these languages (though the required types are quite clever) but letrec does not do this directly! In particular, letrec is closed immediately—you cannot extend it later.
In particular, you don't actually need or want letrec to encode open recursion. That's most of the fun :)
Ok, so my question was, why you need objects at all if you're deciding that your objects should be immutable, and if I'm understanding you correctly, your response is essentially that you need objects if you want inheritance.
Because the extensible open recursion you're talking about only matters in a situation where you're working with base classes and subclasses having different implementations of the same method name and needing dynamic dispatch to determine which one gets called at runtime.
Clojure's hierarchical multimethod system is an interesting alternative approach to this that I think fulfills the semantics you're talking about. I guess you could argue that this is a sort of immutable object system, it's just not called that. http://clojure.org/runtime_polymorphism
Firstly, "object" as a term is really hard to stick a pin in. It's slippery and hard to talk about, so I'm kind of trying to avoid it.
Secondly, "objects" can imply open-recursion which can be used to implement inheritance. That said, inheritance isn't the only thing open recursion is good for and inheritance can be implemented without open recursion.
"Object"s can also imply codata like structures as compared to data like structures. The distinction is blurry to the point of indistinguishability in essentially all languages, but it's important in theorem proving and math and thus shows up in dependently typed languages.
Thirdly, dynamic dispatch is one way to achieve open recursion but it's not the only way. I don't know if dynamic dispatch is useful for things other than open recursion, so offhand I would say "dynamic dispatch => open recursion is being used" but not the other way around.
Clojure's multimethod system, given that it's an implementation of dynamic dispatch, implies open recursion and thus has at least one factor which some people associate with objects. It's immutable (at least to the degree which Clojure is immutable) so I'm willing to call it an "immutable object system", yes. But with all of the caveats I just listed!
In the absence of objects, that's what `letrec` is for. Scheme, OCaml, and SML all have it. In Haskell `let` is `letrec` by default. Clojure has `letfn`. C has forward declarations. Without these features you wouldn't be able to write mutually recursive functions.