SSL/TLS on transportion layer for any links between client and server, and server and database. Encryption for "data-at-rest". Attention to server and database security (i.e. firewall). Redundant and constantly backed up servers and databases. Spam and DDoS protection. MFA supported (optional) for sending transactions and logging in.
Multifactor authentication, ability to lock payout address, deposit addresses that change for every transaction.
Not sure what the big deal is with changing a deposit address for every transaction. In an exchange, your account is associated with your addresses or any new address that is created for any transactions that you make with your account, so there's no reason to create a new address for every new transaction. I can see that this could be beneficial for someone who creates addresses offline outside of any exchange or service in hopes to not let anyone ever link your behavior with any one of your addresses, but an exchange is an exchange. You have an account on an exchange and your addresses will be associated with your account.
However, I don't see this as a big deal at all. What's important is if the exchange is able to obfuscate the transactions that you make by moving the responsibility of transacting on behalf of a user through a "super"-address that is owned by the exchange. This is done by moving your funds into this "super" address. This way, even though it may be possible to determine that your address is linked with a particular exchange, it is not possible to determine the transactions you make. In this way, it adds a layer of security that is unique versus creating your own addresses offline because it's difficult to track what you do, considering the exchange does not store the transaction history that is linked to your account.
EDIT: I can see that if the previous address was deleted and its connection to your account was totally wiped, then I understand changing the deposit address for every transaction would work as a security measure. Not sure if this is good practice tho. Think of it like deleting your private key (wallet.dat if we use qt as an example) and starting all over for every new transaction you make. Is this what bitcoin was designed for? I'm not sure. For me personally, a new address for every new transaction is edging towards paranoia.
