Each customer's transaction will use the same number of output bytes regardless of whether it pays a public key that was already seen on the network or a new public key, and when you go to spend the outputs, it will take the same number of input bytes to spend them whether they paid different public keys or not.
For that reason, it makes sense to use different receiving public keys to differentiate between customers rather than appending an additional output with an OP_RETURN.
To reduce transaction fee as much as possible, you should reduce the byte size of a transaction as much as possible. Here are a few things you might be doing already but which (if you aren't doing them) can help:
Ensure you use compressed public keys (33 bytes) rather than uncompressed public keys (65 bytes).
If you don't need users to pay addresses but can instead get them to pay arbitrary scripts (e.g. you're using custom software or the BIP70 payment protocol), consider accepting payments using pay-to-pubkey (P2PK) rather than pay-to-pubkey-hash (P2PKH); this will save about 24 bytes for each payment.
When segwit becomes available, switch to using it as miners will be able to fit more segwit transactions in a block than they can fit traditional transactions, so they will likely charge you less fee.
Combine multiple payments if possible. If you can get multiple customers to pay you in the same transaction (using something like coinjoin) or if you can pay multiple customers at the same time, you'll produce smaller transactions because you won't need to repeat some fields in a transaction (such as transaction version or locktime). When paying to your customers, you can save quite a lot because you'll only have one change output no matter how many n customers you pay.
