I had this same problem as the OP describes and my solution after a lot of frustration was taking some tutorials on Linux from Youtube. That actually might not be a bad place to start because bash is a programming language (right?). Teaching some simple bash scripts plus navigating the file system wouldn't be the worst intro to programming and it can now be done in Windows.
Yes, bash technically is a programming language - but it's a pretty horrible one in terms of usability, and not the first that I would teach a newbie. Plus, you really don't need it unless your deep into sysadmin stuff.
