Defensive programming and hiring a paranoid sys admin. Sometimes, paranoia is good.

to answer the question, from my view as an outsider:

Programming skills are a plus, because they can review code for secure practices.

Network defense skills. One of the things I am still trying to get time to obtain. Outside of maybe a netgear or McAfee point and click, I've never written a firewall rule, Never black holed traffic from a malicious domain, never setup a reverse proxy. Never setup or monitored a SNORT sensor.

I would say that companies need to start hiring not just the seasoned veterans, but the people with the desire to learn.

This is a trait that's more difficult to come by than you may realize. Everyone here obviously loves this stuff, but in the real world, people try to get into security because they perceive it as glamorous, think it pays well, and/or are of the opinion that there is a high amount of job security. I'm not going to dispute any of those items (granted they can vary greatly based on the specific job), but that opens up the floodgates for many people that are not genuinely passionate about what they do.

To answer the OP, probably the GCIH and GCIA if I had to only pick a couple. If you're on a budget, get started with Counterhack: Reloaded, the Snort book from Syngress, and the Wireshark book.

Thoroughly understand systems and networking. Familiarize yourself with attacks and learn where to look for and how to identify irregularities that may be indicative of malicious activity.

True enough, but companies dont hire based on understanding, they hire based on documentable experience, which you cant get without a job.