I think being a bit of a generalist works well for spouse's jobs. If all you can do is make a perfect widget, then if you move to a place with nary a widget factory in sight, you are SOL. If you work in HR, for example, that's something that can be done anywhere. Jobs dealing with hospitals (even if not directly in patient care) or universities are good, as those tend to be nearly everywhere. I'd also say that jobs requiring any kind of state certification aren't ideal, as the same issues with state bar exams pop up. That said, there seem to be a lot of military spouse's who teach. (My personal guess at why this is is that it is only based partly on the fact that it is a job that is needed everywhere, and that it is also in large part because for whatever reason, military spouses tend to be very kid and family oriented.) And you can be a substitute teacher anywhere (though many states I think still required you to pass the local exam), so that's not a bad gig to consider, but the pay isn't great. You can even be a sub at overseas bases in the DoD school systems. And if she's lucky enough to find a unicorn of a job that allows for 100% telecommuting, she'd of course be set no matter where you go. I'm not sure if that's what you were asking in your second paragraph, but that's my take.
One more comment--you said that "the Navy ALWAYS comes first". Yes and no. It's true to the extent that it is going to force you to do things you and she don't want you to, and that is can be un unstoppable force, no matter how much that interferes with your domestic life. It comes first when filling out your calendar and planning holidays and canceling weekend plans and missing her sister's wedding and moving across the world to a place you don't really want to be. But "the Navy comes first" can become a crutch and an excuse. There have been plenty of times where Husband's job was more urgent than our home life. There have been many times where something important to us or to me got trampled by the forward march of the Needs of the Navy. I've done an hell of a lot of sucking it up. But I've never, ever doubted that I was more important to him than the Navy, even if the Navy was more urgent and more obviously present than my needs.
He's made hard choices, and sometimes they led to disappointment or sadness on my part. But I've had to trust that he's always balanced our home life with his career success and made decisions accordingly, and to trust in his ability and willingness to keep me in mind when making his choices, to come to the conclusions that best represented that balance, and to stand up for me if and when it was necessary and possible. I've always known that if it came down to choosing and I truly needed something from him, that he would move heaven and earth to make it happen, and would sacrifice what he must professionally. (And I've been careful to define "need" very narrowly, so thus far it has never come to that.) Don't let yourself believe the Navy is more important, if you marry this girl, and never allow her to believe that either. The Navy may be bigger and more stubborn, and that's something she'll have to accept, but it should never be more important than your family. The Navy comes first with regard to logistics and planning, but if it ever comes first with regard to the things that truly matter, then you are in the wrong relationship. And she needs to make sure that she knows "working on Saturday because my shop is working and it would be fucked up for me not to be there, so sorry about our theatre tickets" doesn't mean that the Navy is more important than her or that she comes second. It just means that you have faith in her ability to adapt and rebound and this time, you know that when balancing the two, the Navy wins.