"I learned Clojure on my own time in college, and it took some time for me to understand how to deal with things like immutability, laziness, and pure functions."

I suspect much of that time was spent "unlearning" habits from procedural languages.

I know Carnegie Mellon now teaches functional programming as the introductory course, and only introduces advanced topics like "mutability" later. I think that sequence makes it easier for beginners to reason about what their program is going to do and experience less frustration.