With Encrypt-then-MAC, and flexible protocols, do I need to authenticate the authentication?
Though a full analysis would require some details and, presumably, a lot of work, guidance can be obtained from what is done in SSL: at the end of the handshake, a verification step occurs with the Finished messages. These messages are protected with the negotiated algorithms and keys (both encryption and MAC) and, crucially, the contents of a Finished message are a one-way hash of all the previously exchanged handshake messages, thus including the cipher negotiation, the server's public key, the key exchange messages... For instance, see this article for some discussion on the subject. The security of the SSL handshake against various types of active attacks relies heavily on the contents of these Finished messages, and (this must not be forgotten) on their mandatory aspect (client and server ought to refuse to send or receive application data until they have sent/received appropriate Finished messages).

With such a verification, a client (or server) implementing SSL will ensure some security level against active attacks on the handshake which should be at least as great as the weakest of the MAC algorithms that the client (or server) accepts to use. Getting beyond that level (i.e. showing a posteriori that a given connection was protected with the strength of the MAC algorithm which was apparently used, regardless of whether some system would have accepted a weaker MAC) can get tricky.