I know what you are talking about here. I had to harden a production server once upon a time and here are some things I can remember doing:

1. Turned off all necessary services
2. removed all software that was not needed
3. set up iptables: denied ssh brute force attacks, xmas attacks, etc..
4. set up my tcpwrappers to only allow what i needed
5. for ssh i denied root login, only allowed the users i knew needed access, etc.
6. ran nmap localhost to make sure no ports were open i didn’t want open
7. with iptables i only allowed traffic from known IP’s, and then, they had to share their keys with me, so if the ip got spoofed, they’d still need the key to get in.
8. only allow one user to sudo.

your situation is a bit different, but i figured i’d just throw these things out. I wrapped everything in a script so it’d get configured correctly whenever i reinstalled it – if needed.

I didn’t configure selinux because i didn’t understand it well enough.