Is it possible to build a multi-mode "fiber" with an air core so that a significant part of the light's path is through air? The outer sheath made of optically dense material would only be used for internal reflection to "guide" the beam...

To be precise, light can travel through a medium in a straight line, but it bends when it passes from one material to another. The light bounces off the inner walls of the fiber in a zig-zag fashion as it propagates, so it cannot possibly travel at the speed of light. It depends on the index of refraction as mentioned.

No, the speed of light decreases in a medium – in fact, the proportional decrease in speed is the refractive index of the material.

So much for it being constant huh?