Never, ever rely on one tool. Nessus is a good start, but follow it up with additional scanners and audit tools -- the more the better.
GFI Languard, eEye Retina, Lumension Scan (formerly Harris STAT), are all nice to have, though you do have to spend money on getting them. They will have some overlap, but each conducts unique checks as well, so they can only complement each other in assessing how vulnerable a machine is. Of course, you must cross-check each finding with common sense to rule out false positives -- multiple tools assist with this.
In addition to OS scanners, if you're planning on hosting any databases, you might want to consider picking up AppDetectivePro. For websites, check out HP WebInspect or Paros. For network password checks, Cain & Abel is great -- but be sure you have permission to use it, particularly some of the more advanced features.
I recommend checking out some of the open source tool offerings -- nmap is an excellent way to check out what ports are open on a machine, along with netcat to send arbitrary data. Use Wireshark to sniff the network traffic coming from the host, either via a span port or a network tap, and analyze the results -- this often helps identify unnecessary and insecure (like telnet, FTP, and any version of SNMP below v3) network protocols. SNMP read/write strings are basically passwords -- and SNMP v1 and v2 (or 2c) are completely cleartext. Don't use them, and phase them out if you are.
Lastly, but probably most importantly, take a look at the NSA configuration guides for the relevant OS (if they publish one), the DISA Security Technical Implementation Guides from DoD, as well as the Microsoft Security Guides for Microsoft operating systems. These can help you build some validated hardened machines, and should be a starting point for any secure system build. Knowing what your original configuration is goes a long way in determining whether a system has been compromised, or even just whether a particular vulnerability affects your environment.
And just a note -- always, always back up the system before making security-related changes -- particularly if you use the NSA or DISA guides -- they focus on security, not necessarily operations, if you get my drift.