On the other hand I kind of like the solution where the block size is calculated based on mining difficulty. That makes sense from the perspective of mining incentive. If mining becomes less profitable, difficulty lowers, max block size becomes smaller. Thus blocks would have more scarcity and users would need to pay more fees to get transactions into the blockchain, thus giving the miners more incentive. Some kind of equilibrium would happen.

I mean, if the average speed of a full node is the main factor we use to determine this, it really doesn't mean anything other than the fact that we can be reasonably sure that running a full node will remain in reach of regular users. It doesn't actually do much else.

Linking it to mining difficulty would increase mining (our security) if there was more Bitcoin usage and more fees (a higher reward, more miners, more difficulty), thus allowing for a larger block size.

I just changed my mind, I do believe that is actually the best solution. It requires more study for sure, to make sure there isn't some huge loophole. There is obviously the question of how exactly is the max block size calculated from the difficulty.