What determines BTC’s wallet size in bytes?

Does wallet.dat contain every address that I created? Even if I didn’t get any coins from it?

Yes

To be clear, suppose I run bitcoin-qt in Linux, and, in the GUI, I click on Receive then click on Create new receiving address:

1. At this point, no coins are received. Will this immediately generate a new public-private key pair?

Yes. Well, not quite, but in essence, yes. Bitcoin Core pre-generates 1000 keys in a structure known as the keypool. When you request a new address, one of those pre-generated keys is returned to you and another one is generated to replace it in the keypool. This replacement generation can be deferred to a later time, if, for example, your wallet is locked.

How was this public-private key generated?

Depending on when you created your wallet, either randomly, or with BIP 32. Newly created wallets with modern versions of Bitcoin Core will use BIP 32. BIP 32 is a deterministic way to generate keys from a randomly generated seed. Bitcoin Core randomly generates the seed and derives the actual private keys from it using BIP 32.

2. Is this new key pair stored in wallet.dat even before me receiving any payments?

Yes

3. I receive coins on that address. Will this affect the size of wallet.dat?

Yes. When you receive a transaction, that transaction is added to the wallet and this will increase the size of the wallet.dat.

Basically I’m concerned on the size of wallet.dat as I keep creating new receiving addresses.

What determines the size of wallet.dat? It’s about 1.4 MB now. What made it so? What will make it change?

The size is largely determined by the number of addresses you have requested already, the size of the keypool, and the number of transactions that you have, both incoming and outgoing.

Looks pretty linear to me with a slope of 1135.0361445783133 bytes per address. I wonder why is this? Is it because wallet.dat is storing a whole new public-private key pair per address? Or what is happening?

Yes.

If your wallet is unencrypted, each new keypair that is generated will add at least 388 bytes.

If your wallet is encrypted, each new keypair will add at least 120 bytes. This size difference is because encrypted private keys are encoded more efficiently than unencrypted private keys.

I then delted all those addresses, but wallet.dat‘s size didn’t reduce. In fact it even increased!

Bitcoin Core does not allow you to delete addresses. However you “deleted” them, it was likely just hiding them.

If you want a smaller wallet, then you should create a new encrypted wallet. Note that this means creating a new wallet and choosing the option to make it encrypted. Creating a new wallet and then encrypting it after the fact will create extra keys that are never used and just take up space.