The double perovskite material \SFMO has the rare and desirable combination of a half-metallic ground state with 100% spin polarization and ferrimagnetic \Tc$\simeq 420$K, well above room temperature. In this two-part paper, we present a comprehensive theoretical study of the magnetic and electronic properties of half metallic double perovskites. In this paper we present exact diagonalization calculations of the "fast" Mo electronic degrees coupled to "slow" Fe core spin fluctuations treated by classical Monte Carlo techniques. From the temperature dependence of the spin-resolved density of states, we show that the electronic polarization at the chemical potential is proportional to magnetization as a function of temperature. We also consider the effects of disorder and show that excess Fe leaves the ground state half-metallic while anti-site disorder greatly reduces the polarization. In a companion paper titled "Theory of Half-Metallic Double Perovskites II: Effective Spin Hamiltonian and Disorder Effects", we derive an effective classical spin Hamiltonian that provides a new framework for understanding the magnetic properties of half-metallic double perovskites including the effects of disorder. Our results on the dependence of the spin polarization on temperature and disorder has important implications for spintronics.