Before we get into a bunch of specific packages, let's spend some time on what virtually any Linux installation will provide and give some links to documentation that will help you to take advantage of the features.
A great many small businesses will be set up on an Internet connection that gives you one static IP address. Why? Because it is cheap. Whether dial-up, ISDN, DSL, or cable modem, you will frequently want to allow an entire LAN to share this single address.
Virtually all major Linux distributions walk you through setting up such an environment when you install. You need two network cards (Linux does not support routing packets between network alias addresses). For most users, just follow the instructions given during installation. For those who want to do it the hard way, who added Internet after installing their systems, or who just want to know what goes on behind the scenes, consider the following documents:
Firewall HOWTO (http://en.tldp.org/HOWTO/Firewall-HOWTO.html)
This is the "master manual" for using a Linux box as a firewall and proxy box.
Networking Overview HOWTO (http://en.tldp.org/HOWTO/Networking-Overview-HOWTO.html)
A more introductory text that surveys the range of Linux's networking capabilities.
Home Network mini-HOWTO (http://en.tldp.org/HOWTO/mini/Home-Network-mini-HOWTO.html)
Despite the "Home" in the title, this document details this sample scenario: How to run an entire LAN with Internet access given a single IP address connection.
IP Masquerade HOWTO (http://en.tldp.org/HOWTO/IP-Masquerade-HOWTO.html)
This is the "master manual" on the subject of IP masquerade, which is similar to what other vendors refer to as NAT (Network Address Translation).
Masquerading Simple HOWTO (http://en.tldp.org/HOWTO/Masquerading-Simple-HOWTO/index.html)
This is a "quick setup" guide for IP Masquerade. It is a much lighter read than the IP Masquerade HOWTO.
Now let's not kid ourselves. A Linux box makes a good replacement for an expensive router or for an NT box doing this job, but there are innumerable "appliance" class routers that are as inexpensive as the cheapest Linux PC solution, and are smaller and use far less power. Such devices are likely to be a much better choice. The only reasons why I am still using a Linux-based PC for this task are that I have spare PCs (so I didn't have to buy anything) and the Linux box is easily upgraded. If a security problem is uncovered, I can upgrade my Linux PC quickly and cheaply. Some appliance routers can be flash-upgraded. Some cannot. Shop well.
Virtually every Linux distribution installs a Mail Transfer Agent (MTA) by default. Most often, it will be sendmail, although it may be qmail instead.
The Mail Administrator HOWTO (http://en.tldp.org/HOWTO/Mail-Administrator-HOWTO.html) provides ample details.