Few programmers really restrict themselves to one language, since they all have their strengths and weaknesses.
Java is useful, but also fairly strict and rigid; you get less choices about the way you write your programs. You're forced to use OOP and nothing but OOP since literally everything is an object. You're forced to use try/catch since so most things don't bother returning errors any other way. And so-on. It's a whole lot to learn at once just to make the simplest possible program.
I haven't managed to come to grips with Python myself. The way whitespace is actually important in Python code is pretty unusual in a programming language.
Perl is pretty popular and powerful and has lots of modules available. It's also kind of eccentric, being a weakly-typed language with complex data structures and OO.
I'd actually suggest shell scripting, with a modern shell like BASH, so you can get yourself acquainted with variables, arrays, loop structures, functions, and I/O without having someone's pet programming methodology crammed down your throat.
---------- Post updated at 04:47 PM ---------- Previous update was at 04:42 PM ----------
Shell scripting doesn't have data structures though, unfortunately, and can't do a lot of things directly. So once you've learned the basics you could try a more flexible language like C. Properly-written C code can work on lots of different systems.
This is the book I remember most from my college days. I kind of regret giving it away now.
---------- Post updated at 04:49 PM ---------- Previous update was at 04:47 PM ----------
If Ubuntu will work on a virtual machine for you, that'll be good enough for teaching purposes, and better than things like Cygwin which still technically run inside Windows. Might not be the best for teaching though, it's autoconfiguration is a bit overzealous. Perhaps Fedora or SuSe?