There are many tutorials on how to set up a new secured server.
But what if I have to administrate a server someone else had set up some time ago and I don't know much about its configuration yet?
Is there some tool which automatically checks the "usual suspects" or some checklist I can go through to make sure no obvious security holes exist? Are there web services which check remotely for vulnerabilities?
Download Nessus and perform a network check on it. It will tell you about remotely exploitable vulnerabilities.
Also, install Ossec; although it is not its primary purpose, it will find some common misconfigurations (improperly configured accounts for example). And its primary function -- host based intrusion detection -- will help find if someone is trying to exploit vulnerabilities.
I would start with the Center for Internet Security's "benchmark" checklists. These are consensus based checklists compiled by security professionals for a variety of platforms and software packages. Some tools mentioned by the checklists, or otherwise commonly recommended that will aid in your hunt for security issues:
(tcpdump is installed on many linux systems by default, or may be easily installed from a package repository, and has a comprehensive man page)
If this is for the company you work for, make sure that security analysis is authorized by management, and that the scans aren't going to cause any outage or application silliness. Yes a simple portscan can cause problems - portscan older HP Laserjet printers and they'll spit out heaps of paper.
As a very quick first check:
Run
as root. That will show you all services listening on the network:
This might show you stuff you want to shut down right away. Then you can continue with the solutions in the other answers.
For services that need to run, but not be accessible from the outside (such as a local DB server), consider changing the config so it only listens on localhost/127.0.0.1. That way it can only be accessed by local users.
I would check out Bastille-Linux at http://www.bastille-unix.org/, its a set of scripts that you can run and it will check the system settings, file permissions, user setup etc. I've used it once or twice on my own boxes, and if finds issues on default installs (mostly r_x on rsh/rsync utils). It outputs as html/java+curses/flat text.
What distro?
General:
Another good first check is to run nmap hostname from another host on the network. This gives an outsider's view of what netstat showed on the host.
If you are worried, I would recommend following those tutorials you mentioned and rebuilding the server. Especially if you think the other admin might have left something bad. As the new admin, you should know how to deploy whatever service it is running again anyways.
Just make sure you back everything up first, you could image all the partitions to to make sure you really get it right.
If your boss won't let you, then everyone else recommendations sound good to me :-)
In addition to some of the very good responses here, check out http://www.sans.org/. They have some very good documents if you're willing to do a little reading to get a better comprehension of "defense in depth".
Some of the very basic premises tho:
Also try chkrootkit, it comes in the standard repository of most distribution and is anyway very easy to install. It will check your system for many known vulnerabilities, rootkit and worms.
One thing you can do to get a feel for the system is diff the /etc folder against a fresh install (with the same updates applied.) This will tell you what has changed so you can focus your security concerns there.