I think anything above 0.0005 BTC will put you ahead of most transactions.
Thanks, but, I don't want to be ahead, just fair. I have 0.0001713 to my name so far, so watch out Bill Gates...
Any transaction with an output less than 0.01 BTC will require at least a 0.0005 BTC fee or most peers will refuse to even relay it.
If your transaction is made up of SO MANY tiny inputs that it is larger than 10 kilobytes, then you'll need to include a fee of at least 0.0001 BTC (or is is 0.0005 BTC, I can never remember, I'll have to go look in the code again in a bit) PER KILOBYTE or else most peers will refuse to even relay it.