Antiretroviral (ARV)-based pre-exposure HIV interventions may soon be rolled out in resource-constrained Sub-Saharan African countries, but rollout plans have yet to be designed. Here we use geospatial modelling and optimization techniques to compare two rollout plans for ARV-based microbicides in South Africa: a utilitarian plan that minimizes incidence by using geographic targeting, and an egalitarian plan that maximizes geographic equity in access to interventions. We find significant geographic variation in the efficiency of interventions in reducing HIV transmission, and that efficiency increases disproportionately with increasing incidence. The utilitarian plan would result in considerable geographic inequity in access to interventions, but (by exploiting geographic variation in incidence) could prevent ~40% more infections than the egalitarian plan. Our results show that the geographic resource allocation decisions made at the beginning of a rollout, and the location where the rollout is initiated, will be crucial in determining the success of interventions in reducing HIV epidemics.