What came first, transaction or mining? I have been thinking for a while and can't really figure this out..

From my understanding, in Bitcoin network, 'bitcoins' are created when a miner successfully mines a transaction. So this means in order for the network to create a bitcoin, there has to be something to be mined and that something is transaction.

But what I also read, the first transaction was from Satoshi to Hal where Satoshi transferred 10 BTC to Hal. How is the possible since to create 10 BTC, they had to do mining previously which can only be done on previous transaction which makes this transaction not first.. Circular.

Or is it the genesis bitcoin was created without mining? Could be the case, but I am not able to find a reference to that.
Mining was first, as you say, there had to be bitcoins to transact which must have come from mining blocks. The key is, that blocks can be empty. Most early blocks were. And even some blocks now are mined empty, e.g. this one: https://blockchain.info/block/0000000000000000005afd87cdbb34e8126674766c261619044c4c213286d72b

Blocks always contain a Coinbase transaction which pays the reward to the miner regardless of whether there are any other transactions to mine or not.

The incentive for miners to include other transactions in blocks rather than leave them empty is the transaction fees.