Wow, that's quite the write-up, and I'm sure you'll get a lot of seasoned advice here.  Oh yeah, and welcome aboard, stephen.

I'm not former military, myself, so I can't vouch for what they have allowed you to take, or will allow you to take.  As you'll find throughout the forums here (dig around and search a little bit,) you'll see a lot of us giving advice on the different roads we've taken, or recommended to others.  It's VERY largely dependent, as you said, on what you really want to do when you get out.  We obviously can't make a decision for you, so I wish you the best as you do.

That aside...I'd tend to agree, that if you want to begin with general IT Security (not specific to pentesting, auditing, forensics, etc,) then I'd probably start with the basics:  A+, Net+, Security+, UNLESS you're already comfortable enough with your knowledge in A+ and Net+ to bypass those.  However, in any realm of security, the knowledge they teach is still a necessary evil, sometimes, whether from the standpoint of understanding physical or logical network layouts, or even hardware / software configurations and troubleshooting.  But specializing in security, the Security+, as a first step, would be good.  

If you get through that, and feel plenty comfortable with things, then you probably could start studying and working towards CISSP, or you could look more at the CISA / CISM tracks, again, it all depends on where you want to be in 5-10 years, and how you foresee your career advancing.  You're correct in noting that CISSP is very well-known, and in many of the customer environments I work with, they won't hire a security person, regardless of the job description, without it.  Does that mean it's the end all certification to have... definitely not.

If you decide you'd rather work as a consultant, or within a company that specializes in security, then you can focus more on what areas interest you, as well.  You could look at pentesting / ethical hacking, with CEH, GPEN, or OSCP.  If you wanted to move into law enforcement or some other fields, you might prefer to go into Forensics, as that's another field that is booming right now.  (CHFI and other forensic trainings come to mind.)

Ultimately, I'd never say you are 'better off' or 'worse off' to let your future mimic your current work.  I say this as, if you aren't happy with the specific work you do now, you likely won't find any peace in continuing similar employment afterwards.  (Besides, if you totally liked what you do now, the government benefits might far outweigh those you'd find on the outside, and if you were happy in what you do now, or close to it, I'd personally stay put!  - Note: my opinion only)  

My advice to you:  think hard about where you want to be... not next year, or in three years, but in 5-10, or longer.  Look at all the options that are out there and decide what you feel suits you best and what you WANT to do, then look at what career options and training are out there that line up with your goals and objectives.  At that point, if you're having trouble finding things that line up with those objectives, either make a conscious effort to dig further (and obviously feel free to ask us, as we'll definitely help to steer you, if you truly KNOW where you want to go,) or make the decision to look at your 2nd option.  Don't just go into it with one, but prioritize the various options.  Who knows, in the end (this isn't meant to say DON'T go into security,) you might decide that some other IT field, or no IT field at all, is where you truly want to be.  I can only tell you, from personal experiences, that if you don't at least attempt to do what you WANT to do and enjoy, you may regret it down the road.  It took me years to realize I'd missed my calling and enjoyment in IT security, before I came back around, but boy, am I glad I did!  Don't just focus on marketability alone, or you might very well miss the boat.

Good luck, look forward to others' advice, and again, welcome to EH-net!  You'll enjoy the interactions here!