The design of novel cathode materials for Li-ion batteries requires accurate first-principles predictions of structural, electronic, and magnetic properties as well as intercalation voltages in compounds containing transition-metal (TM) elements. For such systems, density-functional theory (DFT) with standard (semi-)local exchange-correlation functionals is of limited use as it often fails due to strong self-interaction (delocalization) errors that are especially large for the partially filled d shells of the TMs. Here, we perform the first comparative study of the phospho-olivine cathode materials LixMnPO4, LixFePO4, and mixed-TM LixMn1/2Fe1/2PO4 (x=0, 1/4, 1/2, 3/4, 1) using four electronic structure methods: DFT, DFT+U, DFT+U+V, and HSE06. We show that DFT+U+V outperforms the other three methods, provided that the onsite U and intersite V Hubbard parameters are determined from first-principles and self-consistently with respect to the structural parameters by means of density-functional perturbation theory (linear response). In particular, we demonstrate that DFT+U+V is the only method that correctly predicts the digital change in oxidation states of the TM ions in all compounds for the mixed-valence phases occurring at intermediate Li concentrations, leading to voltages in remarkable agreement with experiments. We thus show that the inclusion of intersite Hubbard interactions is essential for the accurate prediction of thermodynamic quantities when electronic localization occurs while in the presence of inter-atomic orbital hybridization. At variance with the other methods, DFT+U+V alone is capable to describe such localization-hybridization interplay, and thus opens the door for the study of more complex cathode materials as well as for a reliable exploration of the chemical space of compounds for Li-ion batteries.