The recrystallization behavior, grain growth kinetics, and corresponding hardness variation of homogenized and 80% cold-rolled FeCoNiCrPd, FeCoNiCrMn, and their quaternary/ternary FCC-structured high/medium entropy alloys (H/MEAs) annealed under different conditions were investigated. Experimental results indicate that the grain size and hardness of these H/MEAs follow the Hall–Petch equation, with the Hall–Petch coefficient K_H value being mainly dominated by the alloy’s stacking fault energy and shear modulus. The FeCoNiCrPd alloy exhibits the highest hardness of the H/MEAs at the same grain size due to the largest Young’s modulus difference between Cr and Pd. The grain growth exponent n, kinetic constant k, and activation energy for grain growth Q_G of all H/MEAs are calculated. The k can be expressed by the Arrhenius equation with Q_G, which is attributed to the diffusion rate. The results demonstrate that the Q_G values of these H/MEAs are much higher than those of conventional alloys; most notable is FeCoNiCrPd HEA, which has an unusually lattice distortion effect that hinders grain growth.