We present methods and results from 21-cm Spectral Line Observations of Neutral Gas with the EVLA (21-SPONGE), a large survey for Galactic neutral hydrogen (HI) absorption with the Karl G. Jansky Very Large Array (VLA). With the upgraded capabilities
of the VLA, we reach median root-mean-square (RMS) noise in optical depth of $sigma_{tau}=9times 10^{-4}$ per $0.42rm,km,s^{-1}$ channel for the 31 sources presented here. Upon completion, 21-SPONGE will be the largest HI absorption survey with this high sensitivity. We discuss the observations and data reduction strategies, as well as line fitting techniques. We prove that the VLA bandpass is stable enough to detect broad, shallow lines associated with warm HI, and show that bandpass observations can be combined in time to reduce spectral noise. In combination with matching HI emission profiles from the Arecibo Observatory ($sim3.5$ angular resolution), we estimate excitation (or spin) temperatures ($rm T_s$) and column densities for Gaussian components fitted to sightlines along which we detect HI absorption (30/31). We measure temperatures up to $rm T_ssim1500rm,K$ for individual lines, showing that we can probe the thermally unstable interstellar medium (ISM) directly. However, we detect fewer of these thermally unstable components than expected from previous observational studies. We probe a wide range in column density between $sim10^{16}$ and $>10^{21}rm,cm^{-2}$ for individual HI clouds. In addition, we reproduce the trend between cold gas fraction and average $rm T_s$ found by synthetic observations of a hydrodynamic ISM simulation by Kim et al. (2014). Finally, we investigate methods for estimating HI $rm T_s$ and discuss their biases.
