How is water a worse electric insulator than air? I know I must be missing something here. 
Water has a much higher permittivity than air, which means it has higher (distributed) capitance. That means it can more effectively convert an electric field into charges, and store it. Shouldn't this cause a voltage drop (as V=Ed/q), which is essentually what an insulator/resistor does? If one were to try to block voltage, would an air gap or water gap be better? What about at certain frequencies?
 A: 
That means it can more effectively convert an electric field into charges, and store it.

This doesn't make much sense. 
An insulator is an insulator because it doesn't contain mobile charge.
You're probably thinking of Gauss's Law:
$$\nabla\cdot{\mathbf E}=\frac{\rho}{\varepsilon}$$
But this is not telling you that materials "convert" electric fields into charge. It is telling you that charges are the source of electric field.
But if you consider, for example, a capacitor with two conductors separated by an insulator, the (free) charge will be found in the conductors, not in the insulator.

If one were to try to block voltage, would an air gap or water gap be better?

One important difference between air and water, in practice, is that water is likely to be contaminated with dissolved ionic materials, giving it a much higher conductivity than pure water. 
So water is generally a poorer insulator than air.

What about at certain frequencies?

Another important difference is that the water molecule is an electric dipole, so that it will polarize in the presence of an electric field ($\varepsilon_R > 1.0$), but this effect diminishes at high frequencies (above ~10 GHz) because the mass of the water molecule damps the polarization. So $\varepsilon_R$ of water is indeed frequency-dependent.
Such effects are much smaller in air, since the main constituents of air (nitrogen and oxygen) are not polar molecules.

Let's say pure water vs air then.

So even in ultra-pure water, some of the water molecules will dissociate into H+ and OH- ions. These will allow some ionic transport of current. The conductivity of ultra-pure water is $5.5\times10^{-6}\ {\rm S/m}$ due to this ionic transport (with some variation because the ion concentration depends on the presence of dissolved gases in the water), according to Wikipedia. 
In air, if there are ionic components, their abundance is much less than in water, so that the conductivity is so low that methods of measuring and modeling it are an area for research (example 1). Practically, most conduction in air happens when we exceed the breakdown voltage and create ions in the air by applying a strong electric field. 
