Can different clients have different transaction fees?
The Bitcoin protocol does not require any fee to be paid.

However, the standard client will require varying fees to be paid before the transaction is included in a block or relayed, all depending on the current load (up to 27kB transactions are free unless they are considered spammy, then fees get higher and higher).

Some pools (like Eligius) don't include transactions without fees into their blocks, so that's another incentive to pay something.