Couch to 5k if you've never ran before http://www.coolrunning.com/engine/2/2_3/181.shtml
If you're a geek get an app like Livestrong's which makes it really easy to count calories. There's several online calculators which will give you a good guess on a caloric intake for weight loss though a visit to a nutritionist would get you a more personalized number.
If you don't like counting calories the low carb solutions are a little more "livable" you can go out with friends and get a salad pretty much anywhere. But bread is tasty.