We computationally screen several sulfur-based materials with a spinel crystal structure as potential Al and Mg insertion hosts for Al- and Mg-ion batteries. We evaluate the effect of transition-metal substitution (TM = Ti, Cr, Mn, Fe, Co, Ni) on the key properties determining electrode performance. We systematically calculate the thermodynamic stability, average voltage, binding energy, volume expansion, and Al/Mg diffusion for all compounds. The results suggest that the Ni-based spinel shows a relatively high Al and Mg insertion voltage and low diffusion barriers, and thus is a promising candidate cathode material for Al- and Mg-ion batteries.