You are right that the "second (smaller) capacitor has a reduced ability to store charge" but implicit in this statement is that the voltage across each capacitor is held constant. For example, the capacitance $C$, charge $Q$, and voltage drop across the capacitor $V$ are related by $Q=CV$. If $V$ is constant, larger $C$ means larger $Q$.
When the capacitors are in series this is not that case. The charge in the wire between the first and second capacitors must remain in that segment (the electrons can only move through a conductor and the gaps are dielectrics). This means that $+Q$ is on one capacitor (one side of the wire segment) then $-Q$ must be on the other capacitor (the other side of the wire). Another way to put is that there must be charge conservation on an isolated conductor.
If $Q$ is the same on both conductors (the sign isn't important), then $V_1 C_1 = Q= V_2 C_2$. So a smaller capacitor will have a larger voltage drop across it.
Remember each point of a perfect conductor must have the same potential or it will drive currents to balance out any potential differences. At the same time, the net charge on an isolated conductor is constant due to charge conservation.
Side note
At a certain point, if the voltage gets too large, then the dielectric could breakdown and allow a discharge. If you put overcharge a capacitor (apply a large voltage for long enough) then the gap voltage could get too large.