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.
Notwithstanding any specific ideas on the part of language designers, it bears mentioning that authors and stewards of programming languages are, in the end, pushing a product. So, I might ask why I'd want a camera-phone when my plain phone is a better phone and my camera a better camera, but that isn't going to stop manufacturers of both devices from trying to broaden their product's offering to attract new customers.
Once you look at it from that perspective, then notions of preserving the integrity of the original language become a matter of degrees and tradeoffs. If I'm the author of OOP language AwesomeCode and I see people starting to get interested in new functional language FCode, do I tell my users "sorry, but this is an OOP language only" and risk them going to C# instead to get at its lambas, or do I cave and grudgingly include some of FCode's functionality?
Best Answer
Queues don't functionally compose, and are difficult to implement in a well-performing way without making them mutable.
The very nature of a queue suggests that you put things into it and take things out of it, which is at odds with the immutable nature of functional languages. Oh, sure, you can do the same thing with lists, but generally what you are really doing is composing a new list, not adding to one, and a list doesn't have the special requirement of forcing you to put items into one end and take them out of the other, like a queue does.
All that said, have a look at Okasaki's paper on Purely Functional Data Structures, which does outline a strategy for creating a queue with adequate performance in a functional way.