O Apple Remote Desktop / Screen Sharing é VNC, embora com algumas extensões de autenticação e criptografia. Você está certo de que o VNC não é seguro quando usado em uma rede não confiável, pois todos os pressionamentos de tecla, incluindo as senhas, são enviados sem criptografia. Você pode, no entanto, configurar um túnel criptografado para canalizar o VNC.
A maneira mais fácil de fazer isso é com um túnel SSH. Primeiro, ative o "login remoto" na seção de compartilhamento das Preferências do Sistema, bem como marque a caixa de seleção "permitir visualizadores VNC" que você aponta acima. Então, no computador Windows, baixe PuTTY e encaminhar uma porta de sua escolha (1234, por exemplo) para localhost:5900 no seu Mac. Quando você se conectar com o PuTTY, você será solicitado para o seu nome de usuário e senha do Mac. Em seguida, inicie seu cliente VNC no Windows e conecte-se a localhost:1234 (em que 1234 é a porta que você encaminhou anteriormente). Se você quer ser mais paranóico, configurar um firewall (O Bundled ipfw vai fazer fino; Voar Buttress é uma boa GUI shareware) para não permitir todas as conexões para porta 5900, exceto a partir de localhost (ou seja, o seu endpoint do túnel).
Como um aparte, eu acredito que isso é mais ou menos o que o Screen Sharing faz para fornecer sua conexão Mac mais segura para o Mac, apesar de não usar algo SSH.