The terminology came from the idea of olde tyme gold miners in the days when gold itself was used as currency.
e.g. Get a shovel, go dig a bunch of dirt, find a gold nugget or two and you’ve just created new money which you own outright & can now spend to buy goodies from the local farmer.
The complex puzzle is one which produces a cryptographically valid bitcoin. Other folks don’t pay the miner in bitcoins to go dig; they merely confirm that the fresh data he generated is really a bitcoin, not just digital lead. And they verify the bitcoin by accepting it in payment.
Sorta like the olde tyme miner taking his new nugget to the farmer and saying “I’d like to buy a cow; I’ll pay with this gold nugget”. The farmer wants to satisfy himself the nugget is the right weight, is unadulterated, is gold not pyrite, etc.
The good news is the verification calculation is easy, so any farmer can reliably serve the same function as the olde tyme assay office did: ensuring a nugget is really what it purports to be.
One of the other design shortcomings with bitcoin is over time the miners have gotten fancier mining equipment and can now mine up new coins more rapidly than the designers expected. Not too rapidly, but enough to put some strain on the overall monetary system. Imagine how differently the 1849 California gold rush would have gone if a couple months later somebody showed up with a modern mine’s worth of modern strip mining & gold refining equipment. All those sourdoughs with hand-held pans & sluices would have been blown out of the market overnight.