The relationship between your: resting, maximum and recovery rates has been shown to correlate with your bodies ability to consume Oxygen (VO2max), which itself correlates with the conversion of fats and sugars to ATP, to fuel your muscles. So a few pulse measurements is a fairly commonly used and easy means to assess / estimate fitness. Have a read of "101 Evaluation Tests" for a selection of the more common tests devised to exploit these relationships eg. Rockport walking test, 1.5 mile run, 12 min run, the Harvard, YMCA Queen or Tecumseh Step tests....
Note: The equations all produce ESTIMATIONS, not absolutes, but can be a useful means to measure changes in your fitness over time.
Re:
I'm wondering, what method(s) gives a an accurate measurement of my fitness, without being "expensive".
if you can count your pulse, or have access to a smartphone with a working camera, there are free App's around that will use the phones camera to attempt to measure your pulse (or), and / or also do the maths for some of the various tests. If you don't mind spending a few pennies a heart rate strap can be picked up relatively cheaply, which will permit for a continuous rate to be logged, to allow you to perform even more tests.