You've got the right idea in talking about making something a routine so that it's something you do automatically.
I started running on our elliptical machine a few months back -- 45 minutes a day, 3-5 days a week -- and it's really done me a load of good. Come home from work, fire up last night's Stewart and Colbert, and run while watching them. Gonna watch 'em anyway, may as well do something physical while I'm at it.
Pulled a muscle in one of my hips about 2 weeks ago so I haven't done it as much lately, plus losing my job has thrown off my rhythm, but hopefully I can get back to it this week.
I also used to bike everywhere; I don't know if that's something feasible where you live but it's worth keeping in mind if there IS anyplace you like to go that's in walking or biking distance. Make the extra time to walk or bike and you'll feel better.
As far as becoming a vegetarian: I still eat chicken and fish, but those are better for you than red meat.
You DO still need proteins, of course, and that can mean things like beans, nuts, cheese, and eggs. Go light on the cheese, though; that stuff's generally pretty bad for you. It's entirely possible to be a vegetarian and still have a really unhealthy diet.
Learning to pay attention to calories and carbs couldn't hurt, and it may be worth talking to a nutritionist about that stuff. But it's not going to make a whole lot of difference if you don't exercise too.