I’ll just add my bit,do a good whole body warm up before you start as you’re not just using your legs but your arms will swing,your back will move etc.and have a good warm down when you finish,dont let yourself get cold when you finish even if your melting or your muscles will stiffen up by the next day and you might get a raspy chest.
A short cut I’ve used on the warm down is having a long hot bath with a hot drink to warm up the insides.
Dont run straight after a meal and if you want a crap have it before you set out,when your not yet fit fatigue can loosen the bowels and you dont need something else to be distracted by.
DONT set too ambitious a distance or pace as you probably wont make it,will get demoralised and quit.
Quite honestly you’d have to walk at speed for about ten years to really get any cardio vascular improvement out of it,I’d advise run walk run.
It helps motivate you if you say to yourself I’ll run one lampposts distance and walk two and so on and stick to it for the distance .
If you cant get someone to run/cycle with you try to get a friend interested in your fitness progress,their praise will encourage you and fear of looking a quitter will deter you from jacking it all in.
When you get breathless dont be downhearted,it means that you are using your heart to a greater level then normal which means that each time your breathless your heart is actually getting stronger little by little.
I totally agree with the posters about getting good cushioned running shoes as opposed to expensive fashion trainers,also get someone to look at your running steps.
I knew someone once who ran with an odd stiff gait landing heel first.
This slowed him down,jarred his knees and made him tireder quicker.
I reckon the shoes will probably solve your problem though.
If you can have more then one route to prevent you getting bored and stale.
One last thing you might try,once when I was recovering from a foots worth of broken toes and became totally unfit I got into the habit of going for two runs not too distantly apart in time.
I think that I didn’t allow enough time to let my metabolism slow right down to normal so had a kick start on the second run.
It worked for me.
Finally dont bother with all the special "athletes"vitamin pills and high tech gadgetry,its all bollocks.
Good luck with your endeavour ,ENJOY it and let us all know how you got on.