Symmetric encryption is the foundation for secure communication, and its current iteration in widespread use is authenticated encryption with associated data (AEAD). The AEAD schemes in widespread use today (like AES-GCM) are beginning to show their age in the context of modern workloads whose scale and complexity defies assumptions made during their design over two decades ago. In the last few years, researchers and practitioners have uncovered a series of such critical limitations and responded by proposing and deploying a patchwork of fixes addressing each of these limitations in isolation. This has led to a zoo of incompatible schemes with different security properties which presents a challenge for analysis and interoperability. This thesis argues for simplifying this cluttered landscape of AEAD schemes by building a new generation of clean-slate AEAD schemes targeting modern workloads. First, we emphasize the need for new schemes by introducing new attacks. We demonstrate the first commitment attacks against CCM, EAX, and SIV, and provide more versatile attacks against GCM and OCB3. Then, we specify the first of these new schemes: a new general-purpose AEAD scheme called OCH. It is the first scheme to simultaneously achieve 128-bit multi-user AE security, 128-bit context commitment security, and 256-bit nonces with optional nonce privacy. Finally, we consider the ever-increasing list of special cases that do not admit a general-purpose AEAD scheme like OCH. Rather than specifying and analyzing a new scheme for every special case, we propose a new type of AEAD that flexibly incorporates multiple requirements simplifying analysis and usage.