On the surface (ha) it appears that very low-friction materials are also highly rigid. For example, many gemstones can be polished to be incredibly smooth, and so can some metals. But none of those can survive much torsion without losing their smooth surface (i.e. fracturing, wrinkling). I can't think of any good examples of a low-friction material that is very flexible on a small scale. Is there a direct relation between the two, or is it simply less common to find/create a material that is both very flexible and nearly friction-less?
Yes, there is a broad correlation of inverse proportionality between rigidity/hardness and the ability of such a surface to generate friction.
Imagine a stylus sliding over a soft, rubbery surface. The stylus will indent the rubber surface somewhat (depending on force applied, of course) and this will make it harder to drag the stylus over the surface. Contrast this with a stylus sliding over a hard surface like glass: there is virtually no indentation and it's much easier to slide the stylus over the surface.
Now imagine that instead of a stylus we use sanding paper. In that case there are hundreds of 'styli' per unit of area but the principle remains the same: the 'styli' will indent a soft surface much more than a hard, rigid one. So the softer surface tends to show higher friction forces.
This also explains why friction forces $F_f$ depend on the normal force, for static friction roughly in accordance with:
where $\mu_s$ is the static coefficient of friction and $F_N$ the normal force.
Higher normal forces cause deeper indentation and thus higher interaction (friction).