What did you fly in the Navy?
First thing I would do is check in with any ex-squadron buddies you have that are flying commercially and see how they're doing. Having some friends out in the real world is priceless.
Second, some flights in a 172 or other piston trainer are certainly valuable, but I would find some place in the DFW area with a Redbird box and get some career CFI to get your instrument currency and get your mind thinking in ways you haven't before.
If you're strongly considering the regionals and live in DFW reach out to Envoy recruiting and start a conversation. Given your background you're not too early to start this process. I would also suggest Spirit, but they've recently put the brakes on hiring.