We address the many-body self-interaction in relation to polarons in density functional theory. Our study provides (i) a unified theoretical framework encompassing many-body and one-body forms of self-interaction and (ii) an efficient semilocal scheme for charge localization. Our theoretical formulation establishes a quantitative connection between the many-body and one-body forms of self-interaction in terms of electron screening, thereby conferring superiority to the concept of many-body self-interaction. Our semilocal methodology involves the use of a weak localized potential and applies equally to electron and hole polarons. We find that polarons free from many-body self-interaction have formation energies that are robust with respect to the functional adopted.