Haskell us perfectly fine to start with. It's just Haskell + zsh + git + archlinux + vim + cool-tech aren't things you should learn all at once. Heck, 12 years in, and I'm still lot fluent in all of those.
We can still tell people about cool stuff, just encourage them to take one step at a time, in their own time.
I know Haskell is the introductory programming language of choice at many British universities like Oxford and Cambridge. In the US C, C++ and Scheme (functional) are all in the top 6 most common ( http://cacm.acm.org/blogs/blog-cacm/176450-python-is-now-the... ) so I don't see at all why those shouldn't be good choices.
I feel learning one Algol derived language such as Python followed by Haskell is a good solution. Perhaps even better (of not more painful) would be to learn C followed by Haskell.
We can still tell people about cool stuff, just encourage them to take one step at a time, in their own time.