How do Ethereum clients, like Ethereum Wallet or Eth-Lightwallet, generate unique addresses that haven't been used before, and what is the likelihood that these addresses have been used?
The address is derived from a random private key. The client does not check if it has been previously used because the chance of that happening is nearly zero.
I think the most important phrase in your question is 'what is the likelihood'.
The other answers are correct in determining that there is a 1 in 2^160 likelihood of finding a collision with 100% probability.
Due to the birthday paradox, cryptographers give a hash function with output bitlength 160 a bitwise security rating of 80. This is because with 2^80 addresses, it is more likely than not (i.e the probability is over 50%) that you will have an address collision.
For visual comparison with the above answers, the birthday problem implies a collision will occur with probability 1 in 1,208,925,819,614,629,174,706,176, yikes.
Ethereum Wallet (the official wallet that will use Mist) uses
web3.personal.newAccount to create an account. This is a web3.js call that does the equivalent of
geth account new.
The address space in Ethereum is a 20-byte value (160-bit address space, same as Bitcoin).
what is the likelihood that these addresses have been used?
2^160 or about 1 in 1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976
Ethereum uses addresses that are 160 bits long. The chance that any one address is the same as any other given address is therefore 1 in 2^160. However, due to the birthday paradox the chance that a new Ethereum address is the same as any already existing Ethereum address rises exponentially with every new Ethereum address and is calculated as following:
Chance of a unique pair: ((2^160)-1) / 2^160) = 0.999999999999999999999999999999999999999999999999315772234
Chance of 11,558,357,476,120 unique pairs = 0.999999999999999999999999999999999999999999999999315772234 ^ 11,558,357,476,120 = 0.999999999999999999999999999999999992091451
Chance of some match = 1 - 0.999999999999999999999999999999999992091451 = 7.908549 × 10^-36
As of today (26 Jul 2017) the chance of a new Ethereum address being the same as an already existing Ethereum address is ~8 × 10^-36