i use squid cache proxy (transparent) and iptables for internet access.
squid only works for http request, other request like smtp pop3 ftp etc. are allowed by NAT (iptables). i also use squidGuard to block http access to unwanted sites (porno addware etc.).
i have a standart pc - p4 1.7 cpu, 256 mb ram and 80+80 gig hdd. it works also as a file server.
start to install linux. let us know what s your distro. there are some sites u can get help.
->iptables offical web site
-> a cool iptables script generator.