Remote-Verbindung mit einem Host hinter einem Router

[Deus Figendi]

(Interessant wäre es, von einem Linux Rechner auf einen Windows Rechner zuzugreifen)

Aus genau diesem Grund benutze ich TightVNC, weil das eben plattformübergreifend funktioniert (angeblich, bisher kam ich noch nicht in die Situation).

Der Router hat ja eine externe IP, die er vom Provider erhält und die Hosts dahinter hätten ja lokale IP-Adressen.

Joa, Port-Forwarding heißt das Spiel. Das musst du aber idR beim Endbenutzer durchführen. D.h. er muss auf seinem Router das entsprechend einstellen und das musst du telefonisch machen, weil die meisten Router einen nicht so gerne von außen in die Konfiguration lassen (mag aber auch gehen kommt halt auf den Router an).
Es gibt aber soweit ich weiß auch Dienste, die die Vermittlung übernehmen, d.h. beide Remote-Rechner aggieren als Client zu einem gemeinsamen Server im Netz, der das ganze handelt. Weil das dann beides Verbindungen nach Außen sind geht's auch durch jede Firewall etc. und braucht kein Port-Forwarding weil die Steuerung eine "Antwort" auf eine Anfrage ist.
So einen Dienst kann ich jetzt aber aus dem Handgelenk nicht nennen.