Improving throughput for cell-edge users through coordinated resource allocation has been a long-standing driver of research in wireless cellular networks. While a variety of wireless resource management problems focus on sum utility, max-min utility and proportional fair utility, these formulations do not explicitly cater to cell-edge users and can, in fact, be disadvantageous to them. In this two-part paper series, we introduce a new class of optimization problems called percentile programs, which allow us to explicitly formulate problems that target lower-percentile throughput optimization for cell-edge users. Part I focuses on the class of least-percentile throughput maximization through power control. This class subsumes the well-known max-min and max-sum-rate optimization problems as special cases. Apart from these two extremes, we show that least-percentile rate programs are non-convex, non-smooth and strongly NP-hard in general for multiuser interference networks, making optimization extremely challenging. We propose cyclic maximization algorithms that transform the original problems into equivalent block-concave forms, thereby enabling guaranteed convergence to stationary points. Comparisons with state-of-the-art optimization algorithms such as successive convex approximation and sequential quadratic programming reveal that our proposed algorithms achieve superior performance while computing solutions orders of magnitude faster.