There are few systematic methodologies capable of predicting and leveraging the reserve capacity potential of large populations of Thermostatically-Controlled Loads (TCLs). For such reserves to have economic and technical value, it is essential that demand-side flexibility aggregators and system operators be able to do so quickly and robustly. In addition, aggregators need to ensure minimum TCL users' comfort and end use satisfaction. Part I of this two-part paper introduces an analytical approach to characterize and control the statistical bounds on the potential aggregated response of a population of TCLs, while ensuring users' comfort satisfaction. First, the uncertainty associated with the instantaneous power consumption of a typical TCL is described by a set of random variables and their statistics. TCL statistics are then employed to characterize the exploitable flexibility from a large population of similar devices. From this, a control strategy and parameters are introduced for sporadic (i.e. contingency-type) reserve provision by the population. In Part II, the proposed analytical approach and control strategy are validated for the special case of Electric Water Heaters (EWHs). Further, the trade-off between demand response capacity and EWH users' comfort satisfaction is investigated through several case studies.