openvpn and VNC would be a nice combination.. would work for Linux or Windows.
OR OpenVPN and rdp (rdesktop) to connect to windows desktop from Linux.. rdekstop is a OSS remote desktop client you can use to connect to windows terminal services from Linux. Windows 2000 server, XP, and 2003 Server all have Terminal services built in that can be used for admin. functions.
http://openvpn.net/ - SSL VPN for Linux, Windows 2000/XP and higher, OpenBSD, FreeBSD, NetBSD, Mac OS X, and Solaris
http://www.rdesktop.org/
and of course you already mentioned SSH to connect to a Linux box, which is secure and encrypts the login and password, which you mentioned as a requirement.