In other words (please correct me if I'm wrong), those block-cipher modes that mac the ciphertext (like GCM or EAX) are a better choice than the ones which authenticate the plaintext (like CCM or OCB).
What Moxie Marlinspike gives is a "rule of thumb" rather than a universal statement. The ciphertext may be generated by the attacker; whatever processes the ciphertext first may be working on attacker-chosen data, and if it wasn't designed for that, well, perhaps the attacker can exploit that. MACs were consciously designed to work in that scenario, and so they're always a safe choice.
That said, they're not the only safe choice. The innards of AES-SIV (and its cousins) are also designed to be safe.
And, to comment on something you said early on:
Choosing a proper nonce is a vital part of every symmetric-key encrypted communication, and it is mandatory that every encrypted message has a unique nonce.
Actually, that's not true - one can certainly define secure [1] nonceless symmetric key encryption modes. One favorite of mine is "take the plaintext, append a fixed string of zero bits and send it through a Format Preserving Encryption mode (and if you have an AAD, use that as the tweak); on decryption, check and discard the zeros at the end". We don't do this because it is inefficient, however it does show that it is possible.
[1]: Without a nonce (or changing state between sender and receiver), then duplicate plaintext will result in duplicate ciphertexts. On the other hand, we can often live with this caveat, because in many cases in the real world, we will never exactly duplicate the plaintext.