O HTTP em 80 não atende às suas restrições. Na verdade, nada acontece: a configuração padrão do sistema operacional é totalmente bloqueada sem furos no NAT para o encaminhamento de porta. Você pode usar o controle uPnP para abrir a porta apropriada no roteador, mas isso pressupõe que seu programa seja executado em um nível onde você possa fazer isso.
Se você está fazendo um substituto imediato para o Remote Desktop (o que parece não ser o caso, mas vou mencioná-lo mesmo assim), você ainda teria os mesmos problemas. A Área de Trabalho Remota geralmente tem uma exceção adicionada à política local do Firewall do Windows quando está ativada e um furo inserido manualmente no roteador.
Ah, e um NAT corporativo certamente terá que ser configurado manualmente para permitir o seu programa. Não há como evitar isso se ambos os lados forem NAT corporativos.
O Picking 3389 oferece a você alguma chance de pegar carona em aberturas que podem ser feitas em firewalls para a Área de Trabalho Remota, mas é claro que essas aberturas são feitas porque a Área de Trabalho Remota normalmente está sendo executada lá.
Escolher qualquer porta atribuída a um serviço em particular é um Bad Thing ™, já que a) as pessoas esperam encontrar o serviço lá e b) ele pode estar lá.
O que me leva ao último ponto: por que não usar o Remote Desktop? É um protocolo bastante completo e pode ser mais fácil evitar reinventar a roda aqui.