The electronic structure of surfaces plays a key role in the properties of quantum devices. However, surfaces are also the most challenging to simulate and engineer. Here, the electronic structure of InAs(001), InAs(111), and InSb(110) surfaces is studied using a combination of density functional theory (DFT) and angle-resolved photoemission spectroscopy (ARPES). Large-scale first principles simulations are enabled by using DFT calculations with a machine-learned Hubbard U correction [npj Comput. Mater. 6, 180 (2020)]. To facilitate direct comparison with ARPES results, a "bulk unfolding" scheme is implemented by projecting the calculated band structure of a supercell surface slab model onto the bulk primitive cell. For all three surfaces, a good agreement is found between DFT calculations and ARPES. For InAs(001), the simulations clarify the effect of the surface reconstruction. Different reconstructions are found to produce distinctive surface states, which may be detected by ARPES with low photon energies. For InAs(111) and InSb(110), the simulations help elucidate the effect of oxidation. Owing to larger charge transfer from As to O than from Sb to O, oxidation of InAs(111) leads to significant band bending and produces an electron pocket, whereas oxidation of InSb(110) does not. The combined theoretical and experimental results may inform the design of quantum devices based on InAs and InSb semiconductors, for example, topological qubits utilizing the Majorana zero modes.