Do you want to pay the fee?

[AnonyMint]

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.

Yep. And all of that will be combined with special deals between the big merchants and the client software companies and the miners, and offline transactions, aggregated transactions (transactions from a bunch of Coinbase accounts to a bunch of Mt. Gox accounts combined into a single one-output transaction from Coinbase to Mt. Gox), and CoinJoin transactions (which in many cases lets you combine your transactions with others and lower your fees), and lots of other things some of which I probably can't even currently imagine.

It's gonna be fun.

It's gonna be fun a convoluted mess.

[AnonyMint]

Any one who has shipped million user software preaches K.I.S.S.

You are asking for complexity devolution.

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:

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]

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.

[Cryddit]

so how much should I pay for a fast transaction of 5 bitcoins? or even 2 bitcoins at a time because ill be splitting up all of them out of 28 bitcoins. What will my transaction fee be??

The answer to your question is complicated. But leaving out the math,

If your wallet has been made by you receiving payments of 0.001 BTC at a time, there is no way you can make a 5 bitcoin payment in one transaction because your transaction would exceed the limit on the size of the block.  

If your wallet has been made by you receiving payments of 0.01 BTC at a time, your fee would be 10.3 millibitcoin (or about 80 cents US at current prices) but might take a very long time to confirm because its size is huge in bytes.
                      
If your wallet has been made by you receiving payments of 0.1 BTC at a time, your fee would be 1.1 millibitcoin (or about 8 cents US at current prices)

If your wallet has been made by you receiving payments of 1 BTC at a time, your fee would be 0.1052 millibitcoin  (about 0.8 cents US at current prices). But this transaction will be free if you owned at least 5 coins with an average age of at least 2.77 hours before you make this transaction.

If your wallet has been made by you receiving payments of 10 or more BTC at a time, 0.1 millibitcoin (or about 0.8 cents US at current prices)
But the transaction is free assuming you got at least one of those payments more than 1.4 hours before you make this transaction.

In each case the transaction fee your client asks for may be lower, down to about 9/10 of the above estimate depending on rounding errors and the key size your client uses in the transaction inputs.  As far as I can tell there's no way of knowing this.

[Nagle]

The goal would be to perform all that analysis in realtime and simplify it to the user with something like this:

Recommended fee: xxx mBTC.

With no fee estimated time to confirmation is 12 to 36 hours with 95% confidence.
With fee of xxx mBTC estimated time to confirmation is 1 to 2 hours with 95% confidence.
With fee of xxx mBTC estimated time for to confirmation is 20 to 60 minutes with 95% confidence.
With fee of xxx mBTC estimated time for a confirmation is next block with 95% confidence.

That's something "blockchain.info" could compute. There's a list of Mt. Gox transactions not confirmed for 2 hours, which indicates that the fee required to get a transaction through in less than 2 hours is at least 0.001 BTC.