We present 21cm Spectral Line Observations of Neutral Gas with the VLA (21-SPONGE), a Karl G. Jansky Very Large Array (VLA) large project (~600hr) for measuring the physical properties of Galactic neutral hydrogen (HI). 21-SPONGE is distinguished among previous Galactic HI studies as a result of (1) its exceptional optical depth sensitivity ({sigma}_{tau}_<10^-3^ per 0.42km/s channel over 57 lines of sight), (2) matching 21cm emission spectra with the highest possible angular resolution (~4') from the Arecibo Observatory, and (3) detailed comparisons with numerical simulations for assessing observational biases. We autonomously decompose 21cm spectra and derive the physical properties (i.e., spin temperature, T_s_, and column density) of the cold neutral medium (CNM; T_s_<250K), thermally unstable medium (UNM; 250K<T_s_<1000K), and warm neutral medium (WNM; T_s_>1000K) simultaneously. Of the total HI mass observed, 50% is detected in both absorption and emission. The CNM makes up the majority of the absorbing gas (56%+/-10%) and 28% of the total HI mass including gas detected only in emission. 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 latitude. Finally, although the WNM makes up 52% of the total HI mass, we detect little evidence for WNM absorption with 1000K<T_s_<4000K. Following spectral modeling, we detect a stacked residual absorption feature corresponding to WNM with T_s_~10^4^K. We conclude that excitation in excess of collisions likely produces significantly higher WNM T_s_ than predicted by steady-state models.