As to two-factor authentication,  a very basic way to prevent thefts from an account would be by offering two-factor auth through a confirmation email when the user tries to withdraw funds anywhere. A slightly better (but although cheap, not free) option would be sending out texts. A slightly more expensive but still fairly cheap option would be offering a digital one-time pad dongle (much like the dongles and calculators provided by other online banks).

In my opinion the optimal solution would be automatic (free) two-factor authentication for all users using e-mail or SMS (this is likely cheap enough to be covered by transaction fees), and an optional 'upgrade' to a hardware dongle for a one-time fee/purchase.

EDIT: Almost forgot to mention this. In my opinion two-factor authentication is absolutely essential for any serious exchange that acts like a bank to some degree - and from a business perspective of view it would give you an immediate headstart in the Bitcoin exchange market, it being a more-or-less "exclusive feature".