I want to amend some details in my proposal.

The reserved fees shouldn't be paid as transactions back to the users as that would waste too much space on the blockchain, and even if users aggregate all their fees into one address that changes once in a while, it would still waste space and be bad for privacy.

So I think each output in a transaction should be associated with a reserve fee (could be 0), and it would typically be the difference of f and f*h/p, where h and peak are the current and peak hashrates at the time of the transaction, and f is the full fee paid for the transaction divided by the number of outputs. This reserve fee can only be used when the next time the output is used as an input in a transaction (to preserve fungibility of coins), and it's value would fluctuate based on h/p (hashrate to peak hashrate ratio).

Think of it like this: When you send bitcoin to someone currently it is like sending someone a car without wheels. The car (the btc) needs wheels (fees) to get moved, so with this reserve fee associated with each UTXO you are giving the receiver a chance to send the btc with a fee that will fluctuate according to conditions. If hashrate rises, miners will chip away at the reserve fees created within the past 2016 blocks. At the time of spending the UTXO, whatever is left can be used for the mining fee. Yes in the end miners get all the transaction fees, but the ones they get at times of peak hashrate will be "unconditional" as they will not need a transaction associated with those, so they can fill their blocks with more transactions and take more fees. Also note that the "wheels" will be big for users during rough conditions (falling hashrate) and small during good conditions (rising hashrates).

Edit: I think better not to force the reserve fee to only work with the output it came with, because then people will select outputs based on fee preference, and that can be bad for liquidity or anonymity. Just leave the reserve fees as if they were independent UTXOs, except you can't spend from them; you have to use them as fees for transactions. This would increase the size of the UTXO database, but by a maximum factor of 2.