How big can a wallet get? Say for an exchange that manages thousands of users, and each transaction needs a new receiving address, how much space would thier wallet(s) take. 

I am assuming 100000 users and each user would have about 10000 transactions, so there are about 10^9 keys to be stored. For safety, we would say there are 10^10 keys max that may be stored. 

All I need to know is the size of one key stored in the wallet.
The bitcoinj private keys are 32 bytes long. You would also want some sort of indexing around them so that you could access them efficiently.

If you used a deterministic wallet you would only need one seed and a chain code per customer and generate the addresses as required. I think they are typically 32 or 64 bytes long.