As with any problem found while living in a capitalist society, this one can be solved by throwing money at it. Linksys makes a perfectly workable device that does all of the required magic and can scale up to 253 hosts. The BEFSR41 has four local network ports, so you can hook up up to four computers to your 'net provider with no additional hardware. Its slick little web configuration utility is so simple to navigate that even a total imbecile should be able to set it up, while maintaining many useful options. It can do port forwarding for those of you who want to run a server on one of your machines, mixed static and dynamic DHCP allocations, and even lets you configure a fall-through host for any unmapped ports; useful for a bastion host.
The best part? It works with any platform: Windows, Mac, Linux, Sun, NeXT (yes, I've used it with all of these at once!), whatever.