We use sensitivity analysis to design optimality-based discretization (cutting-plane) methods for the global optimization of nonconvex semi-infinite programs (SIPs). We begin by formulating the optimal discretization of SIPs as a max-min problem and propose variants that are more computationally tractable. We then use parametric sensitivity theory to design an efficient method for solving these max-min problems to local optimality and argue this yields valid discretizations without sacrificing global optimality guarantees. Finally, we formulate optimality-based generalized discretization of SIPs as max-min problems and design efficient local optimization algorithms to solve them approximately. Numerical experiments on test instances from the literature demonstrate that our new optimality-based discretization methods can significantly reduce the number of iterations for convergence relative to the classical feasibility-based method.