We develop a unified theoretical framework encompassing one-body and many-body forms of self-interaction. We find an analytic expression for both the one-body and the many-body self-interaction energies, and quantitatively connect the two expressions through the dielectric constant. The two forms of self-interaction are found to coincide in the absence of electron screening. This analysis confers superiority to the notion of many-body self-interaction over the notion of one-body self-interaction. Next, we develop a semilocal density functional scheme that addresses the many-body self-interaction of polarons, thereby overcoming the limitations of standard density functional theory. Polaron localization is achieved through the addition of a weak local potential in the Kohn-Sham Hamiltonian that enforces the piece-wise linearity of the total energy upon partial electron occupation. Our method equivalently applies to electron and hole polarons and does not require any constraint on the wave functions during the self-consistent optimization. The implementation of this scheme does not produce any computational overhead compared to standard semilocal calculations and achieves fast convergence. This approach results in polaron properties, including the atomic geometry, the electron density, and the formation energy, which are close to those achieved with a hybrid functional that similarly satisfies the piece-wise linearity condition. This suggests that addressing the many-body self-interaction results in a polaron description that is robust with respect to the functional adopted. We illustrate our approach through applications to the electron polaron in BiVO4 , the hole polaron in MgO, and the hole trapped at the Al impurity in α-SiO2.