L'intérêt de proxy + NAT c'est que tu as l'avantage des 2.
L'avantage du proxy (en plus de partager le service concerné sur tous les PC de ton LAN) c'est que ça t'économise de la bande passante en faisant un cache des choses déjà downloadées.
Par exemple, l'utilisateur du PC No.1 a downloadé un MP3 sympa.
L'utilisateur du PC No.2 l'écoute et trouve ça bien.
Admettons qu'il n'y ait pas de partage de fichiers entre les machines de ton LAN, et bien c'est pas grave puisque le MP3 est dans le cache du proxy.
Donc, l'utilisateur du PC No.2 clique dans IE pour DL le MP3, le proxy intercepte la requête, regarde dans son cache si le fichier y est et pouffe transfère le fichier qui est dans son cache vers le PC No.2.
L'avantage du NAT c'est que ça te partage réellement ta connexion pour toutes les applications imaginables qui utilisent le net.
Le proxy ne partage que la connexion qu'à certains services.
Quand je dis les autres applis, c'est par exemple: jeux en réseau, telnet, client mail POP3-SMTP, IRC, soft de partage de fichiers type GNutella, ...
Bien sur, il existe des proxys pour la plupart des services mais à chaque fois il faut paramétrer au cas par cas.
Avec un NAT tu es sûr que tes PC ont accès à tous les services.
Et si tu as peur niveau sécurité, tu peux rajouter un firewall pour bloquer certains services.
Mais bon, si tes PC ne sont destinés qu'à faire du browser pur et dur, dans ce cas, opte pour un simple proxy HTTP. Le plus répandu et gratuit s'appelle SQUID.
Si tu veux un truc simple à paramétrer il y a WinGate sinon.