How can I automate a new linux server's initial setup?

Use a Kickstart or equivalent process to manage the build. Use a configuration management product like Puppet to deploy your settings.

You can also use a little bit of scripting magic to kick off the configuration management at the end of your build to make it a seamless experience.

My script sets a static IP, configures OSSEC and performs a couple puppet runs to sort out all the dependencies then runs a yum update (I'm primarily a CentOS user).

It's possible to cobble together other methods of getting the same results but I've found this to be the most flexible method I've worked with.

Kickstart/Jumpstart, Chef (including chef-solo), Puppet, Salt, shell-scripts, and higher-level scripting languages can all be used to solve this problem.

Honestly, it looks like you have a decent beginnings of a shell script. Start there, and if complexity ramps up, either iterate or look into a beefier product. Personally I've had good experience with Chef.

The key to automating all-the-things is to start small; you don't have to go whole-hog into automation. Pick one pain-point, and make that better. Pick another, repeat.