Some wallets do this by probing the payment first and then using that probed route to make the payment once you confirm (see Bitcoin Beach Wallet for e.g.).

You can also set maximum fees for a payment at the implementation level to avoid being surprised, but I'm not sure many end-user wallets expose this to their users as yet.