Last time I checked mercurial has better windows-support and tooling. And since the concepts generally is the same they should have no issue learning git later on if the need it.
On whether to use Git or Mercurial, my gut suggests you teach Git, but if you have the ability, poll alumns of the program and/or companies who are nabbing grads to see what they have/haven't used. Personally, I've never been around an environment that uses Mercurial, but that's just my particular situation.
Also, the basics of version control should be taught in the very first programming class. You can then expand on the basics in further courses.
Are you talking about high school students?
I guess that they are simply not accustomed to work in command line, given that Windows gives terrible terminal and shell. I would rather expose them to Linux (or maybe BSD), possibly through providing them shell accounts on some server and requiring code to be built primarly there. Then it should not be too difficult to jump from working with files in command line to working with version control in the same command line.