"wanted to get more fit and healthy [...] to shed off the weight or gain muscle"Those are two, three, maybe four different things. The typical marathon runner, for instance, is fit, not fat, but also not muscular, and may or may not be healthy; a sumo wrestler is surprisingly fit and muscular, but also fat, and a body builder is muscular, but need not even be strong (world champion weight lifters look quite different from body builders)
The optimal training program depends on what you want to achieve. That's also what this NY Times reporter seems to be confused about. Training programs focussing on getting fit (especially those focusing on endurance fitness) may have a side effect of looking better in the mirror, but if that is your goal, there are better/faster ways to get there.