Aren't we relying on the body to be inefficient? That is, consume more energy from food than is actually exerted onto the treadmill (or whatever) during exercise.

Thermodynamics provides a lower bound on the amount of energy taken from food, but but couldn't it cost me 2 kcal to put 1 kcal into a stationary bike, while it costs someone else only 1.5?

All conservation of energy says here is that it has to cost at least 1.