Just about any hardware modem should work well for you, you may even be interested in a LAN modem, I think 3COM makes one.
As for your firewall, you are already running one of the most highly respected firewall OS's out there. Depending on whether you are running Linux kernel 2.2.x or 2.4.x will determine whether you use ipchains or iptables /* respectively */. There are a number of other options available too, ranging from NAT and Netfilter to some commercial firewalls for Linux.
A pretty good proxy is Squid, if it did not come with your distro you can get it at http://www.freshmeat.net . It is an outstanding proxy, I would recommend reading the doc's thoroughly before attempting configuration.
A great book that may be at your local library or bookstore on the subject of firewalls is "Building Internet Firewalls, 2nd ed." by Elizabeth D. Zwicky, Simon Cooper & D. Brent Chapman published by O'reilly ISBN 1-56592-871-7
Hope that helped
