I did my BS in computer science at a mid-lower-tier state school - it wasn't like I was all-world Stanford/MIT/CMU or anything. I did a bunch of GRE practice tests and have always been a very strong standardized test-taker so I had that going for me.
I also had cultivated strong references at my undergrad institution. My references were professors I had multiple classes under and that I had actually spent time with during office hours. You may have those sources available to you but I would guess that a decent fallback might be former commanding officers?
The school where I got my MS also had stories about active duty Air Force students coming in full-time for a PhD, mowing through the check-lists of to-do work, and finishing their PhD in the three years the AF gave them to do it.
Your military background may be a strong point in your favor. Also, I vaguely remember that military retirees often had some tuition assistance programs. Grad schools LOVE students with external funding sources. Look into this.
Lastly, it sounds like you have a good story to tell. Tell that story in your application letter!