The hydrated dielectron is composed of two excess electrons dissolved in liquid water that occupy a single cavity; in both its singlet and triplet spin states there is a significant exchange interaction so the two electrons cannot be considered to be independent. In this paper and the following paper, we present the results of mixed quantum/classical molecular dynamics simulations of the nonadiabatic relaxation dynamics of photoexcited hydrated dielectrons, where we use full configuration interaction (CI) to solve for the two-electron wave function at every simulation time step. To the best of our knowledge, this represents the first systematic treatment of excited-state solvation dynamics where the multiple-electron problem is solved exactly. The simulations show that the effects of exchange and correlation contribute significantly to the relaxation dynamics. For example, spin-singlet dielectrons relax to the ground state on a time scale similar to that of single electrons excited at the same energy, but spin-triplet dielectrons relax much faster. The difference in relaxation dynamics is caused by exchange and correlation: The Pauli exclusion principle imposes very different electronic structure when the electrons' spins are singlet paired than when they are triplet paired, altering the available nonadiabatic relaxation pathways. In addition, we monitor how electronic correlation changes dynamically during nonadiabatic relaxation and show that solvent dynamics cause electron correlation to evolve quite differently for singlet and triplet dielectrons. Despite such differences, our calculations show that both spin states are stable to excited-state dissociation, but that the excited-state stability has different origins for the two spin states. For singlet dielectrons, the stability depends on whether the solvent structure can rearrange to create a second cavity before the ground state is reached. For triplet dielectrons, in contrast, electronic correlation ensures that the two electrons do not dissociate, even if the dielectron is artificially kept from reaching the ground state. In addition, both singlet and triplet dielectrons change shape dramatically during relaxation, so that linear response fails to describe the solvation dynamics for either spin state. In the following paper (Larsen, R. E.; Schwartz, B. J. J. Phys. Chem. B 2006, 110, 9692), we use these simulations to calculate the pump-probe spectroscopic signal expected for photoexcited hydrated dielectrons and to predict an experiment to observe hydrated dielectrons directly.