We present 21-cm Spectral Line Observations of Neutral Gas with the VLA (21-SPONGE), a Karl G. Jansky Very Large Array (VLA) large project (~600 hours) for measuring the physical properties of Galactic neutral hydrogen (HI). 21-SPONGE is distinguished among previous Galactic HI studies as a result of: (1) exceptional optical depth sensitivity ($\sigma_{\tau} < 10^{-3}$ per $0.42\rm\,km\,s^{-1}$ channels over 57 lines of sight); (2) matching 21 cm emission spectra with highest-possible angular resolution (~4') from the Arecibo Observatory; (3) detailed comparisons with numerical simulations for assessing observational biases. We autonomously decompose 21 cm spectra and derive the physical properties (i.e., spin temperature, $T_s$, column density) of the cold neutral medium (CNM; $T_s<250\rm\,K$), thermally unstable medium (UNM; $250< T_s < 1000\rm\,K$) and warm neutral medium (WNM; $T_s > 1000\rm\,K$) simultaneously. We detect 50% of the total HI mass in absorption, the majority of which is CNM (56 +/- 10%, corresponding to 28% of the total HI mass). Although CNM is detected ubiquitously, the CNM fraction along most lines of sight is <50%. We find that 20% of the total HI mass is thermally unstable (41 +/- 10% of HI detected in absorption), with no significant variation with Galactic environment. Finally, although the WNM comprises 52% of the total HI mass, we detect little evidence for WNM absorption with $1000Comment: 33 pages, 22 figures, 5 tables; ApJ submitted