Pt-based alloy surfaces are used to catalyze the electrochemical oxygen reduction reaction (ORR), where molecular oxygen is converted into water on fuel cell electrodes. In this work, we address challenges due to the cost of high Pt loadings in the cathode electrocatalyst, as well as those arising from catalyst durability. We aim to develop an increased understanding of the factors that determine ORR activity together with stability against surface segregation and dissolution of Pt-based alloys. We firstly focus on the problem of determining surface atomic distribution resulting from surface segregation phenomena. We use first-principles density functional theory (DFT) calculations on PtCo and Pt3Co overall compositions, as well as adsorption of water and atomic oxygen on PtCo(111) and Pt-skin structures. The bonding between water and surfaces of PtCo and Pt-skin monolayers are investigated in terms of orbital population. Also, on both surfaces, the surface reconstruction effect due to high oxygen coverage and water co-adsorption is investigated. Although the PtCo structures show good activity, a large dissolution of Co atoms tends to occur in acid medium. To tackle this problem, we examine core-shell structures which showed improved stability and activity compared to Pt(111), in particular, one consisting of a surface Pt-skin monolayer over an IrCo or Ir3Co core, with or without a Pd interlayer between the Pt surface and the Ir-Co core. DFT analysis of surface segregation, surface stability against dissolution, surface Pourbaix diagrams, and reaction mechanisms provide useful predictions on catalyst durability, onset potential for water oxidation, surface atomic distribution, coverage of oxygenated species, and activity. The roles of the Pd interlayer in the core-shell structures that influence higher ORR activity are clarified. Furthermore, the stability and activity enhancement of new shell-anchor-core structures of Pt/Fe-C/core, Pt/Co-C/core and Pt/Ni-C/core are demonstrated with core materials of Ir, Pd3Co, Ir3Co, IrCo and IrNi. Based on the analysis, Pt/Fe-C/Ir, Pt/Co-C/Ir, Pt/Ni-C/Ir, Pt/Co-C/Pd3Co, Pt/Fe-C/Pd3Co, Pt/Co- C/Ir3Co, Pt/Fe-C/Ir3Co, Pt/Co-C/IrCo, Pt/Co-C/IrNi, and Pt/Fe-C/IrNi structures show promise in terms of both improved durability and relatively high ORR activity.