Red cabbage (RC) and purple sweet potato (PSP) are naturally rich in acylated cyanidin glycosides that can bind metal ions and develop intramolecular π-stacking interactions between the cyanidin chromophore and the phenolic acyl residues. In this work, a large set of RC and PSP anthocyanins was investigated for its coloring properties in the presence of iron and aluminum ions. Although relatively modest, the structural differences between RC and PSP anthocyanins, i.e., the acylation site at the external glucose of the sophorosyl moiety (C2-OH for RC vs. C6-OH for PSP) and the presence of coordinating acyl groups (caffeoyl) in PSP anthocyanins only, made a large difference in the color expressed by their metal complexes. For instance, the Al3+-induced bathochromic shifts for RC anthocyanins reached ca. 50 nm at pH 6 and pH 7, vs. at best ca. 20 nm for PSP anthocyanins. With Fe2+ (quickly oxidized to Fe3+ in the complexes), the bathochromic shifts for RC anthocyanins were higher, i.e., up to ca. 90 nm at pH 7 and 110 nm at pH 5.7. A kinetic analysis at different metal/ligand molar ratios combined with an investigation by high-resolution mass spectrometry suggested the formation of metal–anthocyanin complexes of 1:1, 1:2, and 1:3 stoichiometries. Contrary to predictions based on steric hindrance, acylation by noncoordinating acyl residues favored metal binding and resulted in complexes having much higher molar absorption coefficients. Moreover, the competition between metal binding and water addition to the free ligands (leading to colorless forms) was less severe, although very dependent on the acylation site(s). Overall, anthocyanins from purple sweet potato, and even more from red cabbage, have a strong potential for development as food colorants expressing red to blue hues depending on pH and metal ion.