Perhaps the most important defining characteristic of Lisp is "Code as Data." You won't get that experience in quite the same way with any other language. In C#, the closest analogue is expression trees.
It is that quality that makes Lisp an excellent language for parsing. It's also the quality that motivated Paul Graham to say of Lisp: "The unusual thing about Lisp-- in fact, the defining quality of Lisp-- is that it can be written in itself." Although self-hosting compilers are nothing new, no language does it quite as elegantly as Lisp does.
Metaprogramming (something in which Lisp also excels) is also a worthwhile thing to learn.
Beating the Averages by Paul Graham
http://www.paulgraham.com/avg.html
I would recommend OCaml.
In my personal point of view, the main basis of modern¹ functional programmings are higher-order functions, a static type system, and algebraic datatypes and pattern matching.
Between a Scheme, a ML and a Haskell, I would choose the ML because I think it's the most relevant to this definition. Scheme doesn't have static typing (there is Typed Racket, but it's not for the scheme beginners), and Haskell has too much other stuff (monads, lazy evaluation...) that, while interesting, may divert attention from the important basis.
SML and OCaml are equally interesting; I'm more used to OCaml, and it has a more "practical" feeling that is nice (but if you really want "practical" to the risk of losing your soul, you may as well pick F#).
Scheme and Haskell are also very interesting languages. Scheme emphasis on macros is interesting, but not directly related to functional programming (it's another of the things in the world you should definitely try, as well as logic programming, stack-based languages, and capability-oriented E).
Haskell is definitely a great language and, I think, a mandatory point for the aspiring gurus of functional programming. But as the core languages of OCaml and Haskell are very much similar (except for lazy evaluation that is distracting for the beginner), it's easy to learn Haskell once you know the basics of OCaml. Or rather, you can concentrate on the weird stuff, and you don't have to assimilate the basics at the same time.
Similarly, once you have seen OCaml, and possibly also Haskell, and still want to learn more, you should look at Coq or Agda. Yet few would recommend Coq or Agda for a first introduction to functional programming...
To make my point clear : I think that learning OCaml (or SML) then Haskell will make you as good a functional programmer as learning Haskell directly, but more easily (or less painfully).
Besides, OCaml and Haskell both have good things differentiating them, and it's interesting to know about the advanced features of both. Just learning Haskell is poorer in that aspect (though of course you could learn OCaml after Haskell; I think it's less logical and will get you more frustrated).
For learning OCaml I would recommend Jason Hickey's book draft (PDF).
¹this definition is controversial. Some Scheme folks will claim static typing has nothing to do with functional programming. Some Haskell people will claim that their definition of purity ("what Haskell does, but no more") is a sine qua non condition for being a functional language. I agree to disagree.
Best Answer
Wait until you'll get to the lexical closures.
Than try to grasp the homoiconic property of the language - this is what makes it really different from the C-likes.
And make sure you'll learn a Scheme with a proper
define-macroimplementation (I'd recommend Racket or Bigloo), not just standard hygienic macros (the latter would not surprise you at all if you're familiar with the C++ templates). Most Scheme textbooks would skip this stuff, unfortunately, but I'd argue that there is nothing nearly as important in Lisps as the proper macros.It is also important to try to understand the purely functional subset of Scheme and learn how to solve all the possible programming problems with it. "Little Schemer" is a good starting point, but not nearly sufficient. Go through "Structure and Interpretation of Computer programs" after it.