I'd suggest Scheme, just because the SICP videos make learning it easy and fun (http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussma...). And, once you get the functional concepts, Haskell and/or Erlang should be relatively easy.
OTOH, if you are really interested in being truly pure, it's hard to beat Haskell. Real World Haskell is a great intro for that language, and it's free online.
If it were the usual programming languages (PHP, Ruby, Python etc), making a choice is relatively easy. For functional languages, I'm not sure where to even begin.
What do you mean by that? Is it just that you know this field better and thus feel better informed, or are you hinting at something else, that I didn't get?
Whereas with functional programming, I am totally new and lost, no clue where to even begin.
No, I didn't hint anything else.