Why does high capacitance correspond to low impedance and vice versa? Physically, why do capacitors increase in impedance when you lower frequency, and vice versa?

Capacitive impedance is $\hat{Z}_C = \frac{1}{j\omega C}$, which means that, for a given AC frequency $\omega$, a large capacitance means a smaller impedance (i.e., more current for a given voltage according to the AC Ohm's Law, $\hat{I}(\omega) = \hat{V}(\omega)/\hat{Z}(\omega)$). Here's the qualitative explanation: if you have a very large capacitance, that means a lot of charge can be stored for a given potential difference, and the capacitor takes a long time to charge up. In an AC circuit, current only passes through a capacitor during the time a capacitor is either charging or discharging. If a capacitor is fully charged or discharged, it acts like an open circuit and does not pass current-- its impedance is infinite. A large capacitance means that (for a given $\omega$ of AC driving voltage) the capacitor will spend more of its time in a charging or discharging mode. A small capacitance means that the capacitor will charge up quickly and spend most of the cycle behaving like an open circuit and so not passing current.

Similarly, for a given $C$, a fast driving wiggle will mean that the capacitor is constantly charging-discharging-charging-..., and so passes more current on average (so has low impedance). In contrast, a small $\omega$ will mean that the capacitor has a chance to charge all the way up or discharge all the way down, and so will be open-circuit-esque during much of the cycle, and hence won't pass much current (so has high impedance).

Both the size of $C$ and $\omega$ matter; impedance is related to the product of them.