The importance of the programs below are in a simi-loose order. If it is at the top, its best that you install it before anything at the bottom, but it may not always be the case. Use your best judgment.
    The NetKit's In the past there was a one stop, get and plug those holes package. However, this package has been broken up into it many pieces, so that programs that were broken, can be put out without having to issue a new Big Netkit. What you need to do is goto the above link and poke around to see if your stuff is out of date. The grab the update and install the bugged program. This might take more time than you want to spend, but you only need to update what you use and have on your system. Remember, if you don't use it, get rid of it. Don't run services that you don't use!

    Tcp Wrappers Many of the daemons that come with many of the Linux Distributions don't do very good logging, and some daemons don't do any logging! So there is Tcp Wrappers. Before any TCP based application can connect, it can be processed by Tcp Wrappers to check to see if the calling site is banned from connecting (via /etc/hosts.allow and /etc/hosts.deny configuration files). Very handy if you want to limit who can connect to your site(S). This comes pre-loaded on many Linux systems.

    Trinux A Linux boot disk security package. It fits on a couple of floppies and can monitor your network. Comes witha bunch of security tools. You should check it out if you need something like this.

    Crack 5.0a Just because you have your passwords shadowed, does not mean some users will not get them! If you force users to have Great Passwords©, then the chances of someone getting your shadow password file via security holes and then using it get into your system will decrease by a very large amount. Crack 5.0a fixes this problem by cracking your passwords with dictionaries and with information found in the GECOS field of the passwd file.
    Not only is it fast (Uses SSL crypt()) it also consumes less memory than previous versions and is very flexible.
    Its does come with some dictionaries, but you should supply some more to make Crack very effective.

    John The Ripper Another password cracker that is suppose to be faster than Crack. I don't know since I have tried it out on a big password file, but it is made by a Solar Designer, who makes some pretty cool security programs, and is known to be a very good programmer, so I believe him. Anyways, it has been hacked to use MMX so it should be pretty fast on our Linux x86 boxes with MMX.
    Oh ya, cracks alot other routines other than One-Way DES that is used to encrypt Unix passwords.

    Tripwire Okay, someone has broke into your system and you have no idea what files were modified or worse yet, replaced with trojans! Well, if you have Tripwire installed, configured properly, and have an up to date configuration file and data file, then you will know. Tripwire scans the system and checks sizes, dates of file, and creates signatures of files. Then it will let you check those files anytime you want, to let you know if they have been tampered with. The downside is that you have to have an up todate data file and have it on a read-only disk for Tripwire to read. (This is not hard to do, remember those flopy drives are good for something!

    COPS 1.04 Although coming to the end of its life, this package from the famous Dan Farmer still has some usefulness. It contains a myriad of security programs and scripts to help protect your system. Grab it and check it out.

    Secure Shell Home Page If your worried about someone Packet Sniffing your rlogin, rsh, rcp, and rdist then Secure Shell is for you. It provides very strong encryption to keep busy hackers from watching your connections. It also provides for authentication, secure X11 connections (This is very cool!), in some cases secure telnet connections and much more. There is even a Windows95/NT (Head over to Vandyke.com for SecureCRT) and Mac Secure Shell! The downside is the other machines you are connecting to must have the Secure Shell Daemon (And not tampered with) properly installed and current. This is not a problem if you run the manchine, because I know you would not soil the Linux Security Homepage by running old and insecure software :). I would highly suggest that you install and use this program. Very recently someone broke into a machine I watch over, and they got in by packet sniffing on another Linux Box. If that person whose password was sniffed had used Secure Shell, they would not have had caused any problems.
    If you are really worried about the physical security of your network and want an encryption package that covers most application-level protocols (FTP, Telnet, etc...), then you should look into Kerberoizing your network. See the Kerberos Users' Frequently Asked Questions

    qmail Okay, off with the gloves and nice words. Lets face it, SENDMAIL SUCKS! Its a bloated crappie, bug ridden, full of security flaws, has no sense of security, peice of shit. Qmail is a lighter, faster, security aware, MTA that does not have any of the security problems of Sendmail (Better known as "Give root mail")
    Qmail is not only built from the ground up to be secure, reliable and stable, but also easy to configure, compile, install, maintain, and post configure.
    Qmail can do everything that Sendmail can do, except give out root access, and it does not require a PHd to configure. As one person told me, "I have a PHd and I still can't configure Sendmail!". I installed and configured Qmail to do Virtual Hosting, Virtual Users, and User Masquarding in less than an hour!

    Fefe's finger daemon A simple and pretty finger deamon that does only what you need. The cool features are: Does not run as root, does not reveal much about the user (No last login, mail, shell, or last login from), gives the user the choice of blocking fingers, has .plan, .project, and .pgpkey files, does not permit system fingers, does full logging and prevents certain kinds of local user attacks. Finally someone gets it right!

    Sendmail For those of you who don't get it, delete sendmail and install Qmail. But if must run Sendmail becuase your slow or your boss won't let you switch over, here is the link the latest Sendmail.

    lsof Lists all open files on your Linux System. Handy to have if some loser opens a bunch of files and "forgets" to close them in an attempt at a denial of service attack. This program will also let you see if someone is running a packet sniffer, since the sniffer writes to a log, and mostly likely an attacker has replaced your Syslogd, w, and ps, you can use lsof to see what programs are writing to what files. Handy!

    pidentd 2.5.1 A improved ident deamon which is more configurable and security aware than the standard Linux installed identd.

    rhosts.dodgy Checks .rhosts for '+ +' and other nasty stuff that should NEVER be there. Written in perl, thus easily configured. Put this script in your crontab and have it check every 15 or 30 minutes (Depends on speed of computer and its use).

    ICMPinfo 1.11 Just like TCP Dump, except that works with ICMP (Ping) packets.