I'm a huge runner, but I really honestly have never run a workout on a treadmill. I can't stand those things. Once you feel confident about your jogging/walking/running abilities, hit the streets!
For workouts I usually alternate easy-hard-easy-hard weekly so that I can recover from hard workouts. My weekly workout (obviously I am young and this is for track, but you can see how it works and apply it to your fitness) usually goes like this:
Monday: 8-12 400s, 70-75 second pace, 1 to 1 rest time. Warm up and cool down.
Tuesday: Easy run, 3-5 miles on trails, 4-8 "flying forties"
Wednesday: 3 sets of 400, 800s. 1x1 rest, strides and cool down
Thursday: Easy run followed by 1 hour of Yoga (it really is amazingly helpful)
Friday: Some type of FastWave or Fartlek type workout, strides, cool down
Saturday: Off, or biking
Sunday: 5-7 miles easy
This has turned me into race shape after only 4 weeks, so the easy-hard mentality works.
Also, diet is important, just get lots of good sugars and carbs, red meat, etc.
And I would definitely quit smoking, that would help a lot.
_WL_