Problems during the first encounter
I was pushed to use Linux forcibly during an undergraduate course. The Red Hat distro UI was so very different from Windows, I could only navigate based on instructions from lecturer slides. The main irk I had was the different file directory, so very much different from Windows! Then there was this weird terminal thingy, and no task manager!
Most confusing concepts between Windows and Linux
Linux seems to have everything somewhere which requires some certain level of code-fu and Google-sensei praying to get. You feel much more powerful when you get it though. Windows with installers seemed more user friendly first, but failures come no matter what level you're at.
First thing to teach
Pros and Cons between distros and branches. How the file system is arranged, and where to look for resources to get unstuck. Also, what the hell are software packages. There were only drivers and programs in Windows.