Floppy Networks (FNs) provide valuable insight into the origin of anomalous mechanical and thermal properties in soft matter systems, from polymers, rubber, and biomolecules to glasses and granular materials. Here, we use the very same FN concept to construct a quantitative microscopic theory of empty perovskites, a family of crystals with ReO$_3$ structure, which exhibit a number of unusual properties. One remarkable example is ScF$_3$, which shows a near-zero-temperature structural instability and large negative thermal expansion (NTE). We trace these effects to an FN-like crystalline architecture formed by strong nearest-neighbor bonds, which is stabilized by net electrostatic repulsion that plays a role similar to osmotic pressure in polymeric gels. NTE in these crystalline solids, which we conceptualize as Coulomb Floppy Networks, emerges from the tension effect of Coulomb repulsion combined with the FNs entropic elasticity, and has the same physical origin as in gels and rubber. Our theory provides an accurate, quantitative description of phonons, thermal expansion, compressibility, and structural phase diagram, all in excellent agreement with experiments. The entropic stabilization of critical soft modes, which play only a secondary role in NTE, explains the observed phase diagram. Significant entropic elasticity resolves the puzzle of a marked, $approx$50% discrepancy between the experimentally observed bulk modulus and ab initio calculations. The Coulomb FN approach is potentially applicable to other important materials with markedly covalent bonds, from perovskite oxides to iron chalcogenides, whose anomalous vibrational and structural properties are still poorly understood.