The reason I don't trade at btc-e, is the difficulty getting USD to the site.
I'm currently trading on bitstamp and campbx mostly, if you want to give them a shot.
To actually answer OP:
What services should a new trader offer?
Multiple currencies, crypto (BTC, LTC, etc.) and fiat (USD, EUR, GBP, RUR, etc)
What banking services should be available in conjunction?
Dwolla is a good place to start, they will want some sort of AML system setup though. US Cash deposits would be nice (ZipZap). Bank transfers, of course.
The one to win the exchange war, I think, is going to be the one that has exchange locations available on Earth, not just on the net.
Is the likes of cloudflare a good idea?
Meh. I'd rather get a 500 or 404 than a cloudflare page, personally, when dealing with an exchange. Cloudflare is good for blogs, and other mostly-static sites; but for a second-by-second, dynamic site like an exchange, cloudflare just pisses me off.
What is an acceptable charging threshold? (I'm out to make a profit, as dirty as it sounds.)
3% max. Anything over, and you will never see most than 1Ƀ in transfers.