When I started learning to program the greatest joy was code=some result. The greatest misery was installation, configuration and bizzaro error messages. In this regard I think Haskell comes out far far ahead. When I first learned Haskell I remember installing Hugs was simple and the REPL worked immediately.
I think that the number one consideration for a first time programming language is the ease with which you can get working software that does something and gives feedback. Clojure has too many leaky abstractions and is not nearly as simple to get up and running. (Aside, I like Clojure)
I think that what I am reading as an implicit question of "should a programmer be initially exposed to the greatest type system known to man in Haskell or the one-true programming language in Lisp" is taking the wrong approach. We should ask "how can I expose a programmer to the joy of making things using only a brain and a keyboard". I suspect that many of the best Haskell and Lisp hackers we have got started on Visual Basic because it was so accessible.
I apologise if my characterisation of your question was wrong. It's not my intention to be offensive or stir up trouble. Those are two great languages to choose from, if you can capture the mind and imagination of a first time programmer with either of them they will be off to a great start.
However, I don't think that clojure is quite as great for teaching functional programming, because it is an eager language unless you explicitly tell it to be lazy exactly where you want it to be, so it doesn't have the performance optimizations that haskell has with recursion (as opposed to tail-call recursion) and it's therefore discouraged to not use tail-call recursion.
Now that's my recommendation for a first functional programming language. For a first language in general, I'd recommend the reverse because with clojure you can actually start doing something practical as soon as you get started, where with haskell it takes a while to get to that point.
But the installation process is different with the two. With clojure, the language is designed around being used with a build system as part of java tradition, which means that you normally can't just type `clj` and get a REPL (at least not with the official distribution). Generally the best way to go about doing that is to install leiningen and make a new project and do `lein repl` in the project directory.
In Haskell on the other hand (with the Haskell platform installer) you can just run the installer and type `ghci` and get a REPL. If you want to run a Haskell program to test it, it's just `runhaskell file.hs` and to compile, it's as simple as `ghc --make file.hs`. But when things get more complicated, even slightly so, Haskell can be an incredible pain to deal with (in terms of compiling and such) whereas clojure, being designed around build systems for large project, scales up just fine.
With Haskell, you'll be learning more than basic lambda calculus. Haskell has a lot of new concepts that traditional-language programmers may have to rewire their brains to think about. Things like lazy evaluation by default, automatic currying, a more advanced type system than most other languages and the concepts that brings like Functors, Monads, and Iteratees. Lazy IO is rough edge which is, as we speak, in the process of being cleaned up by Iteratees.
With a Lisp, you can learn the basic concepts of lambda calculus without having to learn more advanced language features at the same time. You'll tackle things like programming in a declarative language and leveraging first-order functions. Remember, you're trading for-loops for recursion, and for some, that's enough brain rewiring without also worrying about lazy IO.
Lisp allows you to divide and conquer the multitude of language features functional languages have to offer. Why take them all on at once? Once you're comfortable with Lisp, Haskell's true benefits really start to shine. Haskell is by far my favorite language and I find myself hating programming without the features it offers but I'm not sure I would have made it far enough to see it's benefits without learning Scheme first. And learning Lisp is easy. It's a terse language which one could write a small project in in a few weeks and be ready for Haskell.
Haskell is challenging but there's a reason which I'll try to illustrate with an analogy: Calculus is more complex than arithmetic and without a more advanced problem to solve, the added complexity may not be a clear advantage. But you get to a certain point in physics where it simply becomes harder to work in only arithmetic and learning the abstraction of calculus up front pays dividends. Haskell is the same way. I'll end with PG's "The Blub Paradox" http://www.paulgraham.com/avg.html (scroll down).
You can look at the Yesod book, Real World Haskell and "Learn You a" online, i.e. read the complete, updated texts. Thompson's orange "Craft of FP" is a good read also, with methodical (and relatively slow-paced) coverage of all the basics. GHC is piling on language features and libs at a breathless pace, from deferred type checks, limited forms of dependent types, concurrency (async loops, STM, updated thread manager), IO abstractions (conduits), web apps (Yesod)
Clojure is an incredibly well documented (in books) language. I'm looking at the excellent O'reilly and Pragmatic books, and the 2 Manning books ("Joy of" is terrific), all of which came out in the last 4 months and target 1.3. And i will wager that Marick's book will be top notch as well. Unfortunately, these don't have texts online.
If you're going to learn a functional programming language learn a pure one.
None. Learn a language that is appropriate for beginners like Python or PHP.