I imagine this has been thought through and dismissed at some point, but what about a difficulty-adjustment-like thing for block size.
It would aim to maintain a constant-ish fee size by raising and lowering the block limit every two weeks or so.
For example right now in this low fee environment, the algo would lower the block limit to 500kb until fees increased, then go back to 1mb later.