> the shared reads of an immutable value are embarrassingly parallelizable,
This is absolutely true, and Rust lets you do that. You just have to dot your is and cross your ts: https://gist.github.com/steveklabnik/8de9b9b0ae2e45383d85 Rc adds reference counting, to ensure that this reference will be okay for the duration of all of the threads. If you just used a regular old boxed value, one of the threads could invalidate the reference.
That's just one example. As you say, there'll be libraries eventually: people have been focused on the language itself, and given how easy Cargo makes it (will make it) to share libraries, I wouldn't be surprised to see an awesome persistent/immutable data structures library appear.