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.42rm,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<250rm,K$), thermally unstable medium (UNM; $250< T_s < 1000rm,K$) and warm neutral medium (WNM; $T_s > 1000rm,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 $1000<T_s<4000rm,K$. Following spectral modeling, we detect a stacked residual absorption feature corresponding to WNM with $T_ssim10^4rm,K$. We conclude that excitation in excess of collisions likely produces significantly higher WNM $T_s$ than predicted by steady-state models.