Superhydrophobic surfaces display water contact angles greater than 150 degrees in conjunction with low contact angle hysteresis. Microscopic pockets of air trapped beneath the water droplets placed on these surfaces lead to a composite solid-liquid-air interface in thermodynamic equilibrium. Previous experimental and theoretical studies suggest that it may not be possible to form similar fully-equilibrated, composite interfaces with drops of liquids, such as alkanes or alcohols, that possess significantly lower surface tension than water (gamma(lv) = 72.1 mN/m). In this work we develop surfaces possessing re-entrant texture that can support strongly metastable composite solid-liquid-air interfaces, even with very low surface tension liquids such as pentane (gamma(lv) = 15.7 mN/m). Furthermore, we propose four design parameters that predict the measured contact angles for a liquid droplet on a textured surface, as well as the robustness of the composite interface, based on the properties of the solid surface and the contacting liquid. These design parameters allow us to produce two different families of re-entrant surfaces- randomly-deposited electrospun fiber mats and precisely fabricated microhoodoo surfaces-that can each support a robust composite interface with essentially any liquid. These omniphobic surfaces display contact angles greater than 150 degrees and low contact angle hysteresis with both polar and nonpolar liquids possessing a wide range of surface tensions.