Start with something easy and establish a rule that won't ever be broken. If you break a rule once, you'll lose the fight.
My rule, for example, when I started to train more:
- start with 10 crunches every morning and evening
- increase by 2 crunches every day
- no exceptions
When you are at ~2 months in, you can add weight training to it to get stronger.
Additionally, find a sport that you can do once or twice a week that is FUN to do. By FUN I really mean it. There's no point in doing sports if you don't enjoy it.
If you enjoy playing batminton, go for it! If you enjoy table tennis, go for it! If you enjoy Kung Fu, Krav Maga, or whatever ... go for it!
Sports isn't about reaching goals, it's about having fun while doing it. Otherwise, you will not overcome the struggles. Your brain needs a reward, and enjoying sports helps you keep wanting more of it.
That's what I've noticed, too.
But I've also noticed that it makes me crave different foods than when I sit on my ass all day. So, on average, I tend to actually eat less, because I don't have random cravings in between meals.
I doubt that people who are overweight and sedentary only eat "healthy" meals, only too much.