I was about to comment on this subject after having a brief run up to immobility last night. I think exercise/fitness for the player might need some balancing so that it's both (1) harder to build fitness and (2) easier to lose weight.
I wanted to bring up (1) because it felt like even when I would exercise maybe three times a week, and then only two times, I was gaining fitness very consistently up to the point of immobility. I don't know what the best way to approach it is, or if it should count as a problem. Maybe there are diminishing marginal returns above "base" fitness? Maybe the decay back to base should be stronger based on BMI? I'm just ideas-guying.
After checking the code I found a bug that meant exercise wasn't causing as much weight loss as it should (which is now fixed). As I was changing this code, I decided to buff the calories burned when exercising alone as it was the quickest, easiest solution to help players manage their weight until something better can be added.
I think your idea about options in the leveling system might be on the right track. Part of the problem is that the calorie counts of all the food gets massively increased from all the upgrades you can unlock, but the exercise calories remain static (although I do have it so that the larger you are the more calories you burn from exercising).