Fixed fees aren't that bad

I can imagine a black market of fees emerging. Perhaps miners could take side payments from certain addresses in return for prioritizing those addresses.

Good point, not sure how you’d prevent that completely, it seems like you can’t.

But you need to have variable fees for runtime validation (ie. network bandwidth+validation time), and fixed fees for storage.

There are two fundamentally separate fees here: for storage and runtime validation (ie. network bandwidth+validation time). The latter is inherently variable and making it fixed would be absurd, eventually leading to external fee markets where users directly pay stakers/miners the true market price. The former is currently tied to the variable cost which indeed doesn’t make much sense. So they would have to be explicitly separated - ie. only fixed fees for taking up storage.