Senders have no interest in ever attaching any kind of fee, which is one reason we explored child-pays-for-parent for a while. It's not the sender who cares about double spending risk. Left to their own devices, all senders would always attach no fee at all (or rather: whatever the min was to get the transaction relayed to the merchant).

However, receivers do want a fee attached, and ideally we would do this without redundant transactions. Hence, receivers asking senders to attach a fee and effectively folding it into the price that is paid. That is, if you go into a restaurant and the menu says "Burger: 10mBTC" then when you come to pay, what you see on your phone screen is 10mBTC. The fact that actually the shop with receiver 9.9mBTC and the tx fee is 0.1mBTC is hidden in the user interface - creating a situation like many others, where receivers eat a transaction cost. For instance in Europe sales taxes are included in the price, not attached separately later.

There's no need to trust the vendor. If a vendor asks for a ridiculously high tx fee, it will just surface as uncompetitively priced goods/services. Buyers will go elsewhere.

 

That's what fee estimation does, essentially, minus the encoding into blocks. Once you start getting miners telling people what fees are directly you run into cases where they might try to lie about their behaviour or otherwise influence the average. Querying all nodes avoids that problem.