I would recommend Haskell over Lisp, because Haskell will force you to do functional programming, where-as Lisp is less rigid in that regard. In addition the #haskell IRC channel on FreeNode is filled with people who have infinite patience with Haskell newbies and it has an excellent introductory text at http://learnyouahaskell.com/
About two years ago I decided to learn Haskell. Had about 4 false starts and didn't "get" it until my 5th attempt, at which point I figured out what the type system meant and had a bit of a Matrix "I know kung fu!"-moment. Two years of hanging around in #haskell later, I know a billion more things about programming/programming languages and learned type theory (although I still don't grok all conversations there :p).
You may also have luck learning FP with Erlang. It's also functional, but approaches it from a different direction, focusing on reliability and concurrency rather than types and purity. Between Haskell and Erlang, one of them will probably fit your mind better.
I started FP with OCaml, but OCaml makes it too easy to continue writing imperative code when you're actively trying to learn new idioms.
I agree Erlang is also very interesting. I think some of the features looks absolutely fascinating (hot updatable code!), etc. I just haven't found the the time to learn it yet.
I wish Erlang's syntax was more like Haskell, though :\
About two years ago I decided to learn Haskell. Had about 4 false starts and didn't "get" it until my 5th attempt, at which point I figured out what the type system meant and had a bit of a Matrix "I know kung fu!"-moment. Two years of hanging around in #haskell later, I know a billion more things about programming/programming languages and learned type theory (although I still don't grok all conversations there :p).
Some other comments on the usefulness of Haskell:
http://news.ycombinator.com/item?id=1145743
http://news.ycombinator.com/item?id=1145743