Many inorganic pigments contain heavy metals hazardous to health and environment. Much attention has been devoted to the quest for nontoxic alternatives based on rare-earth elements. However, the computation of colors from first principles is a challenge to electronic structure methods, especially for materials with localized f-orbitals. Here, starting from atomic positions only, we compute the colors of the red pigment cerium fluorosulfide as well as mercury sulfide (classic vermilion). Our methodology uses 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 mercury sulfide, this criterion is satisfied because of large transition matrix elements between wide bands, cerium fluorosulfide presents an alternative paradigm: the bright red color is shown to stem from the combined effect of the quasi-2D and the localized nature of states. Our work shows the power of modern computational methods, with implications for the theoretical design of materials with specific optical properties.