Characterization of the differences between biological and random networks can reveal the design principles that enable the robust realization of crucial biological functions including the establishment of different cell types. Previous studies, focusing on identifying topological features that are present in biological networks but not in random networks, have, however, provided few functional insights. We use a Boolean modeling framework and ideas from the spin glass literature to identify functional differences between five real biological networks and random networks with similar topological features. We show that minimal frustration is a fundamental property that allows biological networks to robustly establish cell types and regulate cell fate choice, and that this property can emerge in complex networks via Darwinian evolution. The study also provides clues regarding how the regulation of cell fate choice can go awry in a disease like cancer and lead to the emergence of aberrant cell types.