In your proposal you introduce two separate things. One is the min-fee concept, the other is the min-block concept. I believe the min-fee concept is not adding any value, and all of the value you gain is coming from the min-block concept.
A client can already calculate (locally) the “min fee” (as you have described) and having everyone agree on the min fee formula doesn’t add any value and instead just calcifies it, preventing people from coming up with better formulas.
The min block proposal does have legs though IMO. It allows a user to submit a series of transactions with the same nonce and have them replace-by-fee the longer the transaction sits. As a user, I can submit a transaction with a low-ball price, followed by a medium price 2 blocks later, followed by a high price 10 blocks later. This allows me to have confidence that my transaction will be mined eventually, while still trying for a lower price.
A potential improvement on this would be instead to have the fee be a user-supplied function based on block number. So as a user my fee could be something like block_number - 5900000 * 10^9 if the current block was 5900000. This automatically increases my fee by 1 nanoeth every block starting from current block, thus giving me a strong guarantee that my transaction will eventually be mined while still getting me close to the best price possible. This also reduces the amount of gossip traffic compared to having to submit separate transactions with the same nonce over and over again. Since we already have the EVM, we could make it so the fee is calculated via supplied EVM bytecode with some tight constraints on gas limits for fee calculation. That way people can do whatever formula they wanted.