Since transaction fees are based on the "size" in bytes of the transaction, why is it cheaper use a "sendmany" transaction rather than just making several/many separate "normal" transactions? I don't understand where the "overhead" lies that makes it so much cheaper to "bundle together" transactions like this.
The actual purpose of a regular transaction is to create one or more recipient outputs to pay someone. One could therefore think of the recipient outputs as the "payload" of a transaction, and the remainder of the transaction as the overhead to achieve the transaction's purpose.
Let's assume that we send a single payment in a transaction with one input, the recipient output, and a change output. Assuming that the transaction only uses P2WPKH outputs, the input weighs 68 vB, each output ways 31 vB. The transaction also has a header of 10.5 vB.
This means that the total weight of the transaction is
10.5 + 68 + 31 + 31 = 140.5 vB, i.e. 140.5 vB per payment. Note that your wallet will also need to spend every change output it creates in the future, so we also incur a future "blockspace debt" of 68 vB.
Let's say our wallet performs a high volume of payments, and we have a bit of flexibility when we pay exactly, so we are able to batch multiple payments into one transaction. Instead of making one payment, we perform three payments in a single transaction. Let's assume that our wallet needs to use three inputs to fund the payment:
10.5 + 3 × 68 + 3 × 31 + 31 = 338.5 vB. Even though we still have the same number of inputs per payment, we now only need 112.8 vB per payment instead of 140.5 vB. And we only have to spend a single change output in the future instead of three, which saves us another 2×68 vbytes of future transaction weight.
More often than not, we might have a particularly valuable UTXO in our wallet, and we can fund all three payments with a single input. The calculation now becomes:
10.5 + 68 + 3 × 31 + 31 = 202.5 vB which drops us to 67.5 vB per payment, and still only a single change output.
Note that payment batching has diminishing returns with more payments as the cost per payment approaches the actual size of the output. E.g. for ten payments the weight drops to 41.95 vB per payment, for twenty payments it's 36.475 vB per payment, for 100 payments, it's 32.1 vB. Also, eventually, a single input may not be sufficient to fund your transaction.