The Apple Remote Desktop/Screen Sharing is VNC, albeit with some authentication and encryption extensions. You're correct that VNC is not secure when used over an untrusted network, as all keystrokes - including any passwords - are sent unencrypted. You can, however, set up an encrypted tunnel to pipe the VNC through.
The easiest way to do this is with an SSH tunnel. First, turn on "remote login" in the sharing section of System Preferences, as well as checking the "allow VNC viewers" checkbox you point out above. Then, on the Windows computer, download PuTTY and forward a port of your choice (1234, for example) to
localhost:5900 on your Mac. When you connect with PuTTY, you'll be prompted for your Mac username and password. Then, start your VNC client on Windows and connect to
localhost:1234 (where 1234 is the port you forwarded earlier). If you want to be more paranoid, set up a firewall (the bundled
ipfw will do fine; Flying Buttress is a good shareware GUI) to disallow all connections to port 5900 except from localhost (i.e. your tunnel endpoint).
As an aside, I believe this is more or less what Screen Sharing does to provide its more secure Mac to Mac connection, though not using something SSH.