Ok, from a person who has gone from 250lbs to 170 - most of your weight loss is due to diet.
Secondly - youtube is your friend. I will post a few links later but check out The Lean Machines, they do some great stuff and are very knowledgeable.
Other than that, I sacked off the typical 'gym' and joined a local bootcamp type studio for a more varied training schedule. Things like tyre flips, kettlebells, bodyweight drills (press ups, situps, planking, bear crawls, burpees, star jumps, tuck jumps), dumbell's, bar work, shuttle sprints to name a few things I do.
Also start to run on a regular basis. My run time was miles off when I first started.
I followed the 8 week RN training guide, and didn't move onto the next week until I could complete all the activities that week. So even if I could do all the press up sets etc, if I couldn't run for 20 minutes, then I did the whole week again.
I quickly got my time down.
With a good diet and source of energy, my recovery time decreased which meant I could train more which meant stamina levels increased, meaning I could run further or faster or lift heavier or complete more sets/reps.