What would a new exchange need to be better than the rest? If a new crypto v crypto exchange were to be built and launched. What would tempt you to use it rather than what you currently use? Or what improvements would you like to see from the way things work now.
A popular opinion in the Bitcoin space is that transparency is key for Bitcoin businesses. Bitcoin and it's pseudonymous nature make it very suitable for scams and corruption.

Competitive fees or additional payment options are no longer the key to the success of an exchange. There are so many exchanges that you can almost certainly find what you need feature-wise. However the important question that remains is whether the exchange you found can be trusted with your money.

Proof of Reserve

Fortunately, the nature if Bitcoin's technology also has a positive side with regard to transparency: the Bitcoin block chain is public and everyone can verify it.

This allows for the possibility of exchanges to verifiably proof that they hold all the money of their customers. CoinDesk explains this here. Some exchanges like Kraken have recently published such proof of reserve.

An ideal situation would be for an exchange to provide a method that allows users to constantly verify of their money is still there. F.e. by keeping every customer's coins at a fixed address (this could be quite costly) or publishing a proof of reserve on a weekly or daily basis (this could be done automatically).