Parallel authentication of encrypted data. What AE type to choose?
Use AES-OCB.  It is patented, but now has a free license for any non-military software use.  Unlike most other CAESAR candidates, OCB has been scrutinized for a while now, and meets all of your criteria other than 6 (assuming you have a good AES implementation).  

If the patent is simply too much for you, then use a heavily scrutinized patent-free tweakable block cipher like Threefish in a patent-free mode like Tweakable Authenticated Encryption (TAE) mode.

But, as CodesInChaos points out, you should also break up the message into several pieces and authenticate each piece independently, so you don't waste all day downloading 100 Terabytes that you have to throw away because a single MAC tag at the end doesn't match.  Remember, there are other ways to attack you than just message forgery or breach of privacy - maybe a hacker would be satisfied just wasting your time.