As I understand it, in extremely rudimentary terms, "mining" is the process of verifying transactions on blockchain by solving a complex mathematical puzzle (nonce value). The first "miner" to solve the puzzle (target hash) adds the transaction to the blockchain, and (once a majority of other miners verify their answer) receives a set amount of btc.
Mining is the process of collecting transactions into a block and publishing the block. The solving of the "puzzle" is not related to verifying transactions. It gives the miner the right to publish their block.
What I don't understand, is where the "answer" to said mathematical puzzle comes from, how it is found by a miner...
The puzzle is this:
Find a valid block header for your block such that the hash of the block header is less than or equal to the target value.The only way to find an eligible block header is to make small changes to it (and the block) over and over until the hash meets the criteria.
... and how other miners can verify that answer, without first knowing the answer themselves.... and what confirms an answer to be "correct," (or at or below the target hash)? ...
Each node validate the block by validating the block header and verifying the hash of your block header. If the block and header are valid and the hash meets the criteria, then your block is accepted by the node. If it does not, then your block is rejected.
... What determines the "target hash," ...
The target value was initially set to a certain value, but it is adjusted every 2016 blocks so that the average time between blocks is 10 minutes. Each node computes the target value independently, but they all arrive at the same value because they are doing the same calculation.
... Furthermore, how does answering that puzzle confirm a transaction to be legitimate?
The hashing process is not related to transaction validation. It's purpose is only to allow a block to be added to the block chain. Note that many miners can publish eligible blocks, but the block that is accepted by the majority of nodes is the one that wins in the end.
Finally, if bitcoin mining is the process of verifying transactions, how did Satoshi Nakamoto mine the genesis block? Obviously, without yet having any created bitcoin, there would have been no transactions to verify.
Every block has at least one transaction, but that is irrelevant since validating transactions is independent of creating and publishing a block (however, a block can only hold valid transactions).
I've read some bitcoin skeptics who suggest that the blockchain will become insecure once all btc has been mined, as miners will have little incentive to continue mining once they are only receiving transaction costs as a reward.
Miners come and go, but in the end the security against a 51% attack depends on the value of the block reward, which will ultimately be just the transaction fees. It is possible that fees will not be high enough in the future, but there is no way to know.