I'm 31 years old, overweight, and prior military. I used to run a lot and work out, but I've gotten lazier and lazier about it over the years. I haven't worked out at all in probably 8 to 9 years. I smoke, and I am currently dieting to try to lose some weight. I just quit drinking and I am just nervous about going to the gym again. I really want to start off light and easy on me, but I'm also nervous that if I don't go hard enough I won't see any results. I want to do it, but I could use some guidance on where to start. My cardio is basically negligible and my muscle is pretty damn close as well. What kind of foods should I stick to and exercise regime should I start after so long of a time of not working out or taking care of myself?
Your best option is to start slowly and take small, sustainable steps to also small goals that you can reach relatively soon (so you don't get discouraged). Quitting drinking is a major step (and success!) towards a healthier you. It wouldn't be surprising if that causes some weight loss on its own (depending on how much / frequently you drank).
When it comes to losing weight, diet is, by far, the largest factor in determining your success. You don't need to exercise to lose weight, it just helps put you into a deficit or eat more food while still losing weight. To lose weight you should calculate your TDEE (total daily energy expenditure) and aim to eat 10%-15% less than that in order to lose weight in a sustainable way that won't burn you out. Increasing protein and fiber intake are both good for increasing satiety (so that you can go longer between meals without getting as hungry).
In terms of exercise, weight training (or any resistance training) can have the largest effect on your physique. I would personally recommend a beginner's strength program (StrongLifts 5x5, Starting Strength, Ice Cream Fitness, etc). In the beginning you might be able to lose fat while gaining some muscle (after a while that becomes really hard to do simultaneously). You should try to stick to a beginner's program until you stall out of it. By that time, you can continue with a more intermediate strength program, or look into a hypertrophy (muscle building) based program.
In general, it's a good idea to exhaust your beginner gains on a strength program, as it will allow you to establish true one-rep maxes which will allow you to use a hypertrophy based program more effectively. If you start a beginner strength program with just the empty barbell, you shouldn't have much trouble with starting too fast. You'll progress quickly with the program, but you'll also adapt to the stress of the program quickly too.