  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}=9\times 10^{-4}$ per
$0.42\rm\,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_s\sim1500\rm\,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.
