Editar: esta resposta é válida apenas para uso não comercial, desculpas.
Eu usei o Mikogo para compartilhar áreas de trabalho remotas de forma gratuita - ele fica por perto do NAT fazendo com que ambas as extremidades da sessão se conectem de forma independente ao servidor na nuvem e, em seguida, vincule-as.
Apenas o incômodo é que você precisa fazer com que o usuário carregue uma página da Web, insira o id da sessão e execute o cliente, embora eu tenha conseguido que pessoas não muito técnicas fizessem isso por telefone.
Apenas um dos seus requisitos que eu não testei é o uso com o Linux, apesar de procurar na rede, isso parece ser possível.
Também notaria que as perguntas sobre compras estão fora do tópico, então pensei que isso teria sido encerrado, mas se um usuário de 44k editou a pergunta e a manteve aberta, então, de alguma forma, ela pode ficar aberta.