A new family of magic cluster structures is found by genetic global optimization, whose results are confirmed by density functional calculations. These clusters are Ag-Ni and Ag-Cu nanoparticles with an inner Ni or Cu core and an Ag external shell, as experimentally observed for Ag-Ni, and present a polyicosahedral character. The interplay of the core-shell chemical ordering with the polyicosahedral structural arrangement gives high-symmetry clusters of remarkable structural, thermodynamic, and electronic stability, which can have high melting points (they melt higher than pure clusters of the same size), large energy gaps, and (in the case of Ag-Ni) nonzero magnetic moments.