I've heard various CS teachers say that, when presented with Haskell as a first language, students took to it like a fish to water and could start writing useful code really fast.

My personal experience is that Haskell isn't really all that complex - when you stick to the core, it's actually fairly simple, with a small set of well thought out features (compared to Scala, for example, which I love but has a lot of features). Strangely enough, what I find hard when dealing with Haskell is the syntax, because it's so different from all the languages I've been taught or taught myself in the past. That shouldn't be a problem for people that have little to no previous experience and tackle it with a virgin mind.