Solute additions are commonly used to stabilize nanocrystalline materials against grain growth, and can simultaneously enhance the strength of the material by impeding dislocation emission from the grain boundaries. In this study we demonstrate using molecular dynamics (MD) simulations that the effect of solutes on dislocation nucleation depends on the distribution of solutes at the grain boundary, and can vary dramatically depending on the solute type. Solutes with a smaller positive size mismatch to the host can be more effective in suppressing dislocation emission from grain boundaries than others that have larger mismatch. In particular, although Ag solutes have a smaller misfit with Cu than Zr solutes, the effect of Ag on the dislocation nucleation from grain boundaries in Cu can be larger than the corresponding effect of Zr. These findings are relevant to the search for optimal solute additions, which can strengthen a nanocrytalline material by suppressing the nucleation of dislocation slip from grain boundaries, while stabilizing it against grain growth.