What are the trade-offs between the different algorithms for deciding which UTXOs to spend? When someone would like to make a transaction, their software has to choose which of their UTXOs to spend. Here are a few different ways that one might prioritize which UTXOs get spent.


Oldest UTXOs first
Newest UTXOs first
UTXOs with the smallest amounts first
UTXOs with the greatest amounts first
The Core Client Selection Algorithm: What is the coin selection algorithm?
Others?


What the trade-offs are for the different ways of prioritizing spending of UTXOs? Are some faster? Do some make make the block chain less big (grow less quickly)? Do some make the UTXO set smaller? What about making it so that the user has to pay the least fees? Taking all these factors into consideration, is there a method that is generally accepted to be the best way? 

On possibility, which I like, is to spend the most UTXOs possible while still staying in the 1kb minimum fee limit. That way if nodes that prune the blockchain of STXOs (spent transaction outputs), they can prune more and it makes the blockchain smaller for them. Although, this might cause a small amount of bloating for nodes who keep the whole block chain, so it's a tradeoff.
The challenge for picking a Coin Selection Algorithm is that there are multiple goals to optimize for:
Privacy
The Coin Selection should reveal as little as possible about the user's wallet contents.
Transaction Fee
One wants to minimize the current transaction fee, but also the overall long-term transaction fees.
Non-dust change creation
It would be preferable to create non-dust change.
Reduction of Dust UTXO
Dust UTXO have to be stored on all users' devices and therefore create data volume even on thin clients. It should be a priority to reduce their number.
Unfortunately, these are contradictory to one another, and therefore every solution must find an appropriate balance for itself.

Oldest UTXOs first (FIFO)
Good

Will use up dust UTXO as they come up in your transaction history.

Bad

Gives a date for the oldest UTXO the sender has in his wallet. E.g. reveals how long a user at least has been using Bitcoin (with that wallet), might even be used to guess the amount of bitcoins someone is holding by watching when he spends a known output.
Will not minimize the transaction fee.

Newest UTXOs first (LIFO)
Good

Reveals less information about your wallet than FIFO.
Most of your UTXOs see hardly any action at all (potentially good for privacy).

Bad

Grinds your latest UTXO to dust, until a newer is received or it is used up. Might generate a wallet full of small UTXOs.
At equal or more income than spending, dust will never be consolidated.
Will not minimize transaction fee.
Will link your recent activities by always reusing the newest change output.

UTXOs with the smallest amounts first
Good

Consolidates dust asap.
Continuously keeps number of UTXO at minimum in wallet.

Bad

Reveals lower bound of UTXO value in wallet.
Large input lists (especially as long as dust exists in wallet) cause huge fees and slow confirmation.
Links lots of addresses in your wallet together.
Can be exploited to increase your transaction fee, if people just send you low-value outputs.

UTXOs with the greatest amounts first
Good

Minimal transaction fees.
Likely to create non-dust changes.

Bad

Reveals upper bound of UTXO value in wallet.
Never consolidates dust.
Usually increases number of UTXO in network.

The Knapsack Selection Algorithm used by Bitcoin Core
Good

Often small transaction fees
Random selection of UTXOs seldomly reveals any information about the wallet.
May consolidate dust UTXOs at random.

Bad

Always aims for 10 mBTC change outputs.
With a lot of small UTXOs in your wallet, likely to cause big transaction fees.


(2014:) I have been looking into coming up with a better Coin Selection Algorithm, but haven't found one yet that significantly improves on the Core Client Selection Algorithm.
Here are some ideas to improve it:

When a UTXO is randomly selected, add all other UTXOs associated with the same address as well: less linking of transactions improves privacy, potentially consolidates UTXOs into fewer.
Instead of selecting the smallest change, one could aim to create a change of the same size as the spending target. Assuming that people mostly send useful amounts, this would create new UTXOs of useful value instead of the smallest possible changes as it currently does. It also makes it harder to guess what was the change and what was the payment.
Select UTXO set to minimize transaction fee, instead of minimizing change output.


Update in 2021:

Removed a few allusions to Coin Age Priority as transaction selection policy in block building which was removed in Bitcoin Core 0.12.0 in 2016.
Removed erroneous claim that spending multiple inputs from the same address is cheaper

Note that Bitcoin Core used the Knapsack solver as its only algorithm until 2017, but since then has added an improved algorithm proposed by the author of this answer.