The fee estimation is only based on the past.

It's possible to change the fee estimator to be within a certain mempool constraint also which might be helpful for getting it within the next block but I mainly use the android version of electrum so I don't know how to do it on a PC.

I don't know also why you say you couldn't rbf? Surely they'd just accept the new transaction on the other end?