FEES ARE IMPORTANT TO NORMAL USERS! YOU HAVE TO TELL THEM HOW TO FIGURE OUT FEES!
I don't think it's feasible to tell "normal users" how to figure out fees. The best we can hope for is to tell the people writing the clients how to figure out fees, and for the clients to then automatically suggest the proper fee to the user. An advanced client could have knobs for "increase fees in order to send this transaction faster" and "minimize fees - I don't care if this transaction takes days to complete". The advanced client can have a way to replace a stalled transaction with too low a fee by increasing the fee. The normal user can then just trust that, and/or shop around for the best client.
This. Users aren't going to lookup the number of inputs to determine tx size, calculate priority, and determine the fee by hand. The goal should be making the client perform all this in a transparent manner. Someone did some mockups of an improved tx confirmaiton screen. That should be the goal.
It is also important to note that while TODAY there is no reason to pay more than the min fee the min fee wasn't designed to be a revenue generator. It is a DOS prevention mechanism which raises the cost for a variety of attacks against the network. It is very likely that the fees to timely inclusion in a block will be diverge from the min fee for relaying and so computing the DOS prevention fee is not sufficient to get the "whole story". We are already starting to see this. For the purposes of relaying a high priority tx does not need to include ANY fee. However you still need a miner to include it in a block and since miners limit the amount of free txs in many cases it makes sense for a high priority tx to pay a fee even though it isn't required. I have set my bitcoind to pay the min fee on all txs and have not seen a delayed tx in the last couple months.
The complex part is getting all this information to a user in a simple interface. It can be done but it is more complex then just calculating the min fee. A future "smart" client would look at the average size of recent block history, the break down of fees for tx in those blocks, the number of tx in the memory pool, the priority of those tx and the distribution of fees paid on those txs. For tx which are unlikely to confirm immediately a very smart client would anticipate future tx volume (based on historical norms) and increase the confirmation time accordingly (some of those tx being created AFTER the user will be higher priority and/or have higher fee). The goal would be to perform all that analysis in realtime and simplify it to the user with something like this:
Quote
Recommended fee: 0.02 mBTC.
With no fee estimated time to confirmation is 12 to 36 hours with 95% confidence.
With fee of 0.02 mBTC estimated time to confirmation is 1 to 2 hours with 95% confidence.
With fee of 0.10 mBTC estimated time for to confirmation is 20 to 60 minutes with 95% confidence.
With fee of 0.15 mBTC estimated time for a confirmation is next block with 95% confidence.
Alternative no fee option using highest priority coins (will result in 140 Bitcoin Days Destroyed) has a resulted
[Send no fee] [Send with 0.02 mBTC fee] [Send with 0.10 mBTC fee] [Send with 0.15 mBTC fee] [Send alternative no fee]
With no fee estimated time to confirmation is 12 to 36 hours with 95% confidence.
With fee of 0.02 mBTC estimated time to confirmation is 1 to 2 hours with 95% confidence.
With fee of 0.10 mBTC estimated time for to confirmation is 20 to 60 minutes with 95% confidence.
With fee of 0.15 mBTC estimated time for a confirmation is next block with 95% confidence.
Alternative no fee option using highest priority coins (will result in 140 Bitcoin Days Destroyed) has a resulted
[Send no fee] [Send with 0.02 mBTC fee] [Send with 0.10 mBTC fee] [Send with 0.15 mBTC fee] [Send alternative no fee]
Of course we are nowhere near that but the goal would be to abstract all this from the user and allow them to make a choice as simple as choosing a delivery option when buying a product online (pay more = faster, pay less = slower).
Two very important improvements to the fee system are safe transaction replacement and a concept called "child pays parent". With the later some merchants (especially those which don't need immediate payment) may simply tell users to send without a fee and the merchant bundles all the unconfirmed tx includes a single large fee and gets priority access into a block.