> What was worse was that there was no objective way to measure progress so I didn't even know if it was doing anything.

I agree that not being able to measure progress is horribly demotivating. But I find the opposite, that exercise is one of the few areas in my life where I can objectively measure progress. For example:

  Body weight
  Resting heart rate
  5k run time
  Longest distance run without stopping
  Max weight / number of repetitions / duration for strength exercises

These are all objective measurements which can be tracked over long periods of time and directly correlate with the amount and quality of training that one does. I have found that this is the best long-term way to motivate myself.