I was using a .45uM filter on a solution, and while water could pass through it quite easily, air does not pass through at all. If you try to pass air through the filter it is impossible. So, does that mean that water is smaller than all the molecules in air, or is it something else? I would have thought something like O2 would be smaller than H20.

Once the filter is wet it is difficult to get air through it. That's because the air would have to form lots of little bubbles to get through. The effect of surface tension makes this difficult.