This is the main point of contention as I see it. I hold that getting newbies to consistently attain 85-95% of their maximum heart rate just isn't going to happen most of the time.
That's really not a problem, at least not physiologically. One cannot sustain this level of effort for more than a few minutes, which, it turns out, is enough. You'll need a heart rate monitor (cheststrap + wristwatch), get on a treadmill and warm up gently. Work out at around 4 x 4 minutes, with 3-4 minutes of lower intensity walking or jogging in between. Why 4 x 4 minutes, and not something else? Because this has been found to strike the balance between compliance, or self-compliance, as the case may be, and physiological benefits.
For an optimal workout, for a pro athlete you would want to do something like 30 or so 15-second intervals, but sticking to such a regimen is unrealistic for newbies if you don't have someone coaching you. It takes more willpower than most people actually have, so it doesn't really work. Most people do have just enough willpower to work hard for four times four minutes, and then go home.
Walking, jogging or running at a steady pace for an extended period of time at intensities below the lactate threshold does not confer dramatic health benefits. It's still good for you, but you won't be able to feel your body noticably improving from week to week.
At four minute intervals you are working beyond your lactate threshold, so walking, jogging or running is not sustainable at this level of effort for an extented amount of time. Push too hard, for too long and you'll can get nauseous or just feel terrible from burning lactate instead of glucose, if so you need to hold back. 4x4 minutes with 4 minutes rest in between should give an increase of around 0.5% per workout in VO2max, if memory serves. You should notice obvious increases in endurance within a few weeks. One needs to commit to any exercise regime, including this one, but it's not too hard or painful if you're doing it right.
One should also do strength exercises in addition to interval training. Your 3x5 schedule sounds great for this.
Edit: Dangerously misleading on one crucial point.
This started out as a short reply to the Less Wrong post Minimum Viable Workout Routine. Unfortunately I was unable to summarise my points sufficiently, so this reply grew into a post of it's own. I realize that the following is a bit rude to the original poster, and I apologize. Minimum Viable Workout Routine seems to be backed solely by anecdotal personal experience. The majority of the post, which addresses strength training seems decent, and not obviously wrong. However, the following paragraph is dangerously wrong:
Leaving this uncontested could be dangerous to your health. As we shall see, cardiovascular capacity is indeed important to survival and longevity. It is also quite easily trainable, it needs not be soul crushingly frustrating, and it should not be overlooked.
A couple of cool findings from the physiology of exercise:
Instead of having me trying to convince you, we'll take a look at the science, and see what we find.
You can assume with reasonable confidence that the findings are valid, well-corroborated, and furthermore, the findings quoted in this post have been found to apply to the general population, to the untrained, the athlete, the elderly, and the ill, even though I'm only able to present here a selection of these results.
Human physiology, and its response to exercise is surprisingly stable across genders, race, age and physical fitness. What works for the well trained athlete will also work for the utter newbie, the obese, and patients with heart disease.
Strength training is also important to health, increases in maximal strength of the large muscle groups tends to cause large increases in endurance, as measured in time to exhaustion. Why? Because if your muscles have to work slightly less hard at each movement, relative to the one repetition maximum of the muscle, you can work at moderate to high intensities for much longer.
So, let's first see that a brief strength training intervention can dramatically increase endurance:
Maximal Strength Training Improves Running Economy in Distance Runners
So a maximal strength training exercise of maybe 10 minutes, 3 times per week, for eight weeks, resulted in an increase in time to exhaustion of ~20% in well trained runners. So increases in strength can lead to large gains in endurance.
Cool, because endurance training is important. Endurance training makes you die less often, on average:
Exercise Capactity And Mortality Among Men Referred For Exercise Testing
If you want to live long and prosper, you should train your body, most importantly your heart, to be able to work hard when you can. So that it can work hard for you when it must fight for your life. With that, let us have a look at endurance training in the elderly:
Effects of High-Intensity Endurance Training on Maximal Oxygen Consumption in Healthy Elderly People
Why is this interesting? Well, it seems that old people respond the same to vigorous exercise, as do young people.
But! They tend to do less of it, and consequently they gradually suffer worse health. I'm oversimplifying, but there is a causal path from physical inactivity with old age, (not because of old age) which leads to deterioration of health which leads to death. If you are reaching retirement age, or you know people who are, try to get them to move their butts before it's too late. And don't stop moving. Don't stop moving even if you suffer heart failure. Let's have a look at the effects of vigorous training in patients with heart disease:
Interval and Strength Training in CAD Patients:
So this is what heart patients get in return for sixteen minutes, three times a week for two and a half months. If you're still breathing, and able to move by your own power, you are capable of the level of cardio exertion that leads to significant adaptation. You don't necessarily have to run fast, you just need to be able to get your heart rate to 85-95% of your maximum heart rate, repeatedly. For a CAD patient or an overweight person, this could mean a brisk walk. If you're out of shape, you don't have to fly across the terrain at amazing speed for your heart to get all excited.
How, exactly, does endurance training keep people healthy and alive?
Repeated intervals of brief, but high intensity endurace training causes increased stroke volume of the heart, when working at peak capacity. This carries over into the resting state, and lowers your resting pulse, your blood pressure, increases your maximal oxygen uptake, increases your working capacity when healthy, makes you less likely to get ill. If you get ill, your heart will be better at keeping you alive.
Closing thoughts:
Should you trust my opinion? I've only taken a single university course in exercise physiology. You should not trust my opinion, and this is not professional advice. But my opinion is backed up with well-corroborated scientific findings, and you should probably trust those.
The course i took was excellent. The teaching professors were were former national team coaches, they have applied their research to great effect on healthy, untrained students, CAD patients, COPD patients, youth athletes, elite athletes and billion dollar soccer teams.
Pursuing a regime of maximal strength training and high intensity interval training, you should see evident and mutually reinforcing gains in strength and endurance, and you'll not stop seeing benefits, even at the level of 100 million dollar soccer players. (Endurance and Strength Training for Soccer Players)
An final anecdote of my own:
I used to find physical exercise dis-congruent with my geek identity, I found it boring, painful, useless. Learning the very basics of exercise physiology, along with some nerdy details makes working out seem important. It helps to know why I'm doing it, I know what the expected effects are, and the expected sizes of the effects, how to avoid training fatigue, track my heart rate, track my progress, and on the whole, see that I'm on track to results like those mentioned in the studies above. I find it fun to try and figure out what is happening, and approach working out as something of a puzzle to be solved. Exercise, or the lack of it, is an experiment in health.