Você pode fazer isso no terminal. Mas primeiro a placa de rede do seu laptop deve suportar AP (ponto de acesso). Confira esta pergunta no fórum do ubuntu como fazer isso. Além disso, você encontrará lá como configurá-lo. Mas no caso de você querer compartilhar a conexão do mesmo cartão que você está conectado com o outro laptop Windows, isso pode ser feito apenas com alguns cartões apenas. Confira esta questão (como mencionado em um dos comentários acima também).
Agora, se isso não funcionar, eu recomendaria outra maneira ...
Tente usar o laptop ubuntu para compartilhar a internet e o windows como um "repetidor". Algumas pessoas dizem que funciona (como eu nunca tentei eu mesmo), usando esta ferramenta de microsoft .
Se isso não funcionar também, do que a única maneira de usar duas placas wireless diferentes no laptop ubuntu, ou conectar ambos os laptops com um cabo LAN (compartilhando a internet através do cabo), e com o laptop ubuntu compartilhar a conexão via sem fio.
Agora, para a segunda pergunta ... não tenho certeza se acertei, mas o proxy está configurado no roteador? Se assim for, aqui está alguma ajuda sobre como configurar navegadores no Squid. E se você quiser configurar uma conexão sem fio para usar o proxy do seu telefone windows, verifique este tutorial .
Agora, se você quiser criar um servidor proxy baseado no Squid, para que o Windows Phone possa se conectar, não tenho certeza de como você pode fazer isso no Ubuntu, mas como o Windows é muito semelhante a um servidor proxy normal. Verifique este tutorial para isso.
P.S.
Caso eu esteja fora de algum lugar ou não tenha entendido a pergunta corretamente, por favor me avise, então talvez eu possa ajudar você mais longe.