The freezing of water into ice is a key process that is still not fully understood. It generally requires an impurity of some description to initiate the heterogeneous nucleation of the ice crystals. The molecular structure, as well as the extent of structural order within the impurity in question, both play an essential role in determining its effectiveness. However, disentangling these two contributions is a challenge for both experiments and simulations. In this work, we have systematically investigated the ice-nucleating ability of the very same compound, cholesterol, from the crystalline (and thus ordered) form to disordered self-assembled monolayers. Leveraging a combination of experiments and simulations, we identify a "sweet spot" in terms of the surface coverage of the monolayers, whereby cholesterol maximises its ability to nucleate ice (which remains inferior to that of crystalline cholesterol) by enhancing the structural order of the interfacial water molecules. These findings have practical implications for the rational design of synthetic ice-nucleating agents.