While distributed on-chip voltage regulation offers an appealing solution to power delivery, designing power delivery networks (PDNs) with distributed on-chip voltage regulators with guaranteed stability is challenging because of the complex interactions between active regulators and the bulky passive network. The recently developed hybrid stability theory provides an efficient stability checking and design approach, giving rise to highly desirable localized design of PDNs. However, the inherent conservativeness of the hybrid stability criteria can lead to pessimism in stability evaluation and hence large over-design. We address this challenge by proposing an optimal frequency-dependent system partitioning technique to significantly reduce the amount of pessimism in stability analysis. With theoretical rigor, we show how to partition a PDN system by employing optimal frequency-dependent impedance splitting between the passive network and voltage regulators while maintaining the desired theoretical properties of the partitioned system blocks upon which the hybrid stability principle is anchored. We demonstrate a new stability-ensuring PDN design approach with the proposed over-design reduction technique using an automated optimization flow which significantly boosts regulation performance and power efficiency.