Many inorganic pigments contain heavy metals hazardous to health and environment. Much attention has been devoted to the quest for non-toxic alternatives based on rare-earth elements. The computation of colors from first principles is a challenge to electronic structure methods however, especially for materials with localized f-orbitals. Here, starting from atomic positions only, we compute the color of the red pigment cerium fluorosulfide CeSF, as well as of mercury sulfide HgS (classic vermilion). Our methodology employs many-body theories to compute the optical absorption, combined with an intermediate length-scale modelization to assess how coloration depends on film thickness, pigment concentration and granularity. We introduce a quantitative criterion for the performance of a pigment. While for HgS this criterion is satisfied due to large transition matrix elements between wide bands, CeSF presents an alternative paradigm: the bright red color is shown to stem from the combined effect of the quasi two-dimensionality and the localized nature of 4f-states. Our work demonstrates the power of modern computational methods, with implications for the theoretical design of materials with specific optical properties.