Why is this conditional in my fragment shader so slow?
Pixels get grouped into little squares (how big depends on the hardware) and computed together in a single SIMD pipeline. (struct of arrays type of SIMD)

This pipeline (which has several different names depending on the vendor: warps, wavefronts) will execute operations for each pixel/fragment in lockstep. This means that if 1 pixel needs a computation done then all pixels will compute it and the ones that don't need the result will throw it away.

If all fragments follow the same path through a shader then the other branches won't get executed.

This means that your first method of computing every 16th pixel will be worst case branching. 

If you want to still down size your image then just render to a smaller texture and then upscale it.