La forma más económica y simple es hacer que el PC que tiene Linux enrute tu red a Internet mediante NAT (Network Address Translation) siguiendo un procedimiento conocido como IP Masquerading. De esta forma el propio PC se comporta como un router. Puedes encontrar más información al respecto (en inglés) en
http://www.tldp.org/HOWTO/IP-Masquerade-HOWTO/. Usando el software que te recomiendo, con que el PC que está corriendo Linux sea un 386SX o superior y tenga un lector de floppy disk de 1.44 será suficiente (ni siquiera necesitas que tenga disco duro). Esto es lo que necesitarás:
1 hub o concentrador de 4 puertos.
1 tarjeta de red Ethernet 10/100 (convencional) para cada PC.
1 modem para el PC que está corriendo Linux.
Respecto al software, te sugiero Coyote Linux (
http://www.coyotelinux.com/) por su facilidad de instalación y por supuesto, es gratis. En las propias páginas de Coyote Linux encontrarás mucha más información sobre la instalación. Sobre la forma de configurar el PC que tiene Linux como router, encontrarás más detalles en
http://www.linuxrouter.org/. Para el resto de los PCs, usa cualquier versión de Windows que sea igual o superior al Windows 3.11 for Workgroups (95,98, ME, NT, 2000 o XP). Si vas a usar Windows 98, te sugiero que mejor uses el 98SE pues Windows 98 original te dará algunos problemas. Y por supuesto, siempre tienes la alternativa de usar Linux en cualquiera de los PC.
Algo interesante para tu red sería que instalaras Sambar (
http://www.sambar.com/). Además de funcionar como servidor web (para que puedas tener servicios de intranet), también se puede encargar de llamar periódicamente a tu ISP, enviar y recibir correo de todos los PCs y luego actuar como servidor de correos POP y webmail para distribuir el correo a los usuarios de tu red. Es un producto excelente y fácil de configurar.
Espero que esta información te resulte útil. Si necesitas algo más no dudes en avisarme.