[sea6ear]

If you really want something to change the way you think, I would suggest Scheme while reading SICP "Structure and Interpretation of Computer Programs". I believe MIT makes the newer version of the text available online, and the old MIT Open Courseware lectures that go along with the old version are very good. Also, the book "The Little Schemer" is a great way to get a handle on recursive thinking. Scheme is also very similar to the low level abstract syntax tree format of some kinds of compilers, so if you are interested in compiler theory it may be useful to know.

Erlang can be sort of considered a "Scheme with syntax". However, it is also somewhat weird, and if you're just starting with a functional language, you might as well go for Scheme.

I personally don't know that I'd recommend Haskell as a starting functional language. If you want to learn Haskell, I might suggest stating with Erlang as a baby untyped Haskell, and then move up to Haskell.

Also, Javascript is more functional than is generally realized, however, it's functional flavor may be more obvious after you have been exposed to an explicitly functional language.

One last thought, if you are interested in Web programming, Clojure is a functional flavored version of Lisp that runs on the JVM, and has a web framework called Compojure that seems well regarded.

[glassx]

I started with Erlang, to pick up the basics of functional style, and then tried Haskell. It was a breeze, but I alreadt had C#+LINQ and Ruby experience.

[diolpah]

This. SICP is a fantastic book. Buy it, then read it. Twice. Or more.