How does water freeze and crystallize on a cold superhydrophobic surface?
As acknowledged in your question, there are a large number of factors at play here. The most basic of these is that there are three fundamental mechanisms by which freezing of a droplet can initiate when in contact with a superhydrophobic surface: 1) heterogeneous nucleation where an ice freezing nucleus (IFN) is present in the water droplet, 2) heterogeneous nucleation where the superhydrophobic surface serves as the IFN, and 3) homogenous freezing of the water droplet.  

An excellent demonstration of the first or third scenario above (it is not clear from the article which is actually the case) is given in video format from an article published in Nature$^1$. In this experiment, the water droplet is evaporatively cooled until freezing initiates at the water/air interface, and continues without adhering to the aluminum-based superhydrophobic surface.  

Whether or not freezing will initiate at a superhydrophobic surface depends upon the degree of supercooling, the presence or absence of potential IFN within the water droplet, and the potential for the specific material (the superhydrophobic surface) to serve as IFN. It would seem that the latter of these would be unlikely, except that a surface being hydrophobic doesn't mean that it is equally icephobic. Basically, the more the surface resembles the crystalline structure of ice, the more likely it is to act as an IFN. 

Please don't hesitate to ask for any clarifications in the comments below.

1) Thomas M. Schutzius, Stefan Jung, Tanmoy Maitra, Gustav Graeber, Moritz Köhme &amp; Dimos Poulikakos, Spontaneous droplet trampolining on rigid superhydrophobic surfaces, Nature 527, 82–85 (05 November 2015) doi:10.1038/nature15738