Depending on your security needs, you can even go further - two linked bastion hosts. The public-facing bastion host has two NICs, one for Internet, the other one as a 1:1 link to the second bastion host (having two NICs again, the first is the endpoint to the 1st bastion host, the 2nd connects with the internal network).

Then make the public bastion host a VPN gateway so that the SSH bastion host can only be reached by SSH. This way, even if the first bastion host/VPN gateway appliance gets compromised, an attacker still needs a security flaw in the SSH bastion host.

Oh, and I forgot: regularly update your systems! Subscribe to various security mailing lists - this is the fastest way of learning about vulnerabilities.

And if you're running web apps: clearly separate the individual virtual hosts using either a full chroot solution or stuff like suexec/suphp from each other; same goes for the database users. Only grant necessary DB privileges (e.g. no need to give a webapp db user the GRANT capability in MySQL).

If you're dead paranoid like me, set up the application servers as VMWare (or other virtualization) servers, and for each webapp, create an own virtual machine. Then, link the VMs with an internal network and create a "bridge" server running nginx/apache/squid as reverse proxy (which can also serve as SSL terminator to avoid spreading HTTPS certificates over dozens of machines!). Maybe use special IDS software to detect/prevent common attacks like SQL injections. This way, if your web-app gets hacked, at least the attack won't easily spread to the other servers.

Thanks for all the advice! You've definitely introduced me to some things I've never considered before. Now to cram more learnings into my brain... :)

:D Yet another thing that just came to my mind: use different operating systems and software stacks on the two bastion hosts (or, at least, OS A on the bastion host and OS B on the "normal" hosts). You may, for example, choose a *BSD variant for the bastion host, and a Linux variant for the web hosts.

Simple reason: if the software stack of one of the hosts gets compromised (e.g. a 0day is found in OpenSSH), then the other bastion host cannot be compromised with the same exploit.