I second the recommendation for C25K. Remarkably simple program, and there are free apps for your phone that literally, in a synthesized voice, tell you to run, walk, and cool down at the proper intervals. Mine sounds like a Marine DI.
I've already finished it on a treadmill and am repeating the program, outside. Outside is harder. This morning's run was W3D2.
I recommend it for nearly anyone.
Is there a site for Convict Conditioning you would recommend?
I have resistance bands and I really do not use them much. I am a big fan of dumbbells. They offer the classic resistance of weight, both on the upswing and the downswing, they do not spring back too fast like the bands, and you get the independent movement from both arms (unlike a barbell which can make a strong arm stronger and a weak arm not as strong). The dumbbells will take up more space than the bands, especially once you start getting stronger and need to purchase heavier weights.
I also completed a C210K plan (same as C25K but I did that once before and got lost when I finished). This will help keep you on track with a routine. I still run one day and weights the next and try to get a rest day in once in a while.
I looked up the the training program for Chris Evens, the actor who plays Captain American right now. I figured I'd look at what they used to get him it to trim. Not overbuilt but damn good trim. They used free weights because it does not isolate the mussel groups.
That being said, any system that you will stick to is better then nothing.
As to your diet, you may just want think about the calories in your sweets and give your self an allowance. Or simply write down every time you have some. Just noting it, and seeing when you last had some may be the extra will power you need to cut back some.
I would highly recommend a solid adjustable bench and a set of adjustable dumbbells. You can do all of the basic lifts and build over all balance and core strength as well. Start with light weight and adjust them heavier until your ready for a rack and a barbell. Machines allow your body to cheat too much by not forcing you to balance the weights. If you go with a dumbbell and bench you wont be in it too deep if you end up not using the equipment.
Diet is going to be your biggest challenge. You will not slim down or make any gains unless you are eating properly. That means trying to cut sweets, sweetened drinks, preservatives etc from your diet. Try to eat whole foods high in protein, fiber, good fats, and low in bad carbs. If you cut most canned and processed foods out of your diet and eat more natural stuff that you cook yourself you can lose up to 20 lbs in the first month from your body purging the crap out.