First, thank you for serving our country in the Marine Corp!
Your service is appreciated!
If you've ever done any fly fishing for bass, then some saltwater fly fishing will be similar. I won't make recommendations for specific outfits, as we all cast differently & how a particular rod feels to one person may not be the same to another. The rods I use in the salt are TFO & Redington brands in 8, 9 &/or 10 wt & I have no complaints with either brand. You're budget will certainly affect your choices, but there are many rods on the market that you could try.
You should be ahead of the game some with the fishing experience you already have, and particularly since you've already been fly fishing.
Like with other tackle, no single fly rod (size, length, line rating, etc.) will fit all situations & conditions. IMO, for what you intend, you could use anything from a 6 wt, up to a 10 wt. However, again my opinion, an 8, 9 or 10 wt would be a good choice. There are advantages & disadvantages to each.
If you can locate others in the area who fly fish, that could give you the chance to perhaps cast some different rods & get advise on what others are using.
There are also dozens of flies that will work for Reds & trout. Whatever you select, you want some different hook sizes, perhaps from 4 up to about 2/0, and both weighted & unweighted flies. Weights should vary too. Some should have weed guards as well, especially crab or shrimp patterns.
Basic flies will imitate baitfish, shrimp &/or crabs. Styles such as Clouser Minnows, Lefty's Deceivers & Seaducers are all great general purpose flies. You might also check out patterns by Tim Borski, which are more specific for the type of sight fishing you want to do. There are many other patterns that will work as well. Again, your budget will probably determine what you choose. If you tie flies, so much the better, as you can tailor them to your own preferences. You'll want some that are both light in color, some that are dark, and even some that might be colorful. Colors such as pink & chartreuse are usually good, as are tans, browns & shades of olive. Basic black, & white are always good too.
I did a quick look at Parris Island via Google Earth & looks like you have a lot of places that might be fishable water. I would guess it would depend on access. Check out Youtube for sight fishing to redfish or trout, that should give you some ideas about how to go about it. Like I said, it can be much like bass fishing.
Admittedly, I have yet to catch a Redfish on a fly. I've caught them on bait & on lures, but not a fly. I have caught Black Drum on flies in NC, which I've been told is very similar. Much of the fishing I do for LM bass & Striped Bass is in tidal waters, and is similar also I think. I've caught numerous trout on flies in the past, but my opportunities with Redfish have so far been limited. I have a trip planned to VA next month, and perhaps will remedy my lack of success with fly caught Redfish.
I also searched what is nearby to you as far as fly shops. Looks like there is at least one in your area. Even if you don't purchase your gear there, it won't hurt to go & look at what they have & talk with them. Better shops will freely give good advise. Pay particular attention to flies they may have on display. Such shops will often have the most productive patterns for the area & will usually advise on what is the best approach for using them. It doesn't hurt to purchase a few either to get the best advise!
If you don't tie flies, once you get an outfit, let me know. I'll be more than glad to send you some flies to get you started!( I tied commercially for many years.
) Again, thanks for serving this great country!