Rational and systematic grid partitioning can significantly accelerate system recovery and improve restoration success rates. This paper investigates a robust optimization model and algorithm for power grid partitioning that accounts for the impact of the recovery process in new power systems. First, a robust optimization model for grid partitioning is constructed, with the objective of minimizing a weighted sum of outage losses during recovery, tie-line power flows between partitions, and differences in partition restoration times, while incorporating comprehensive operational constraints. The model also considers frequency and voltage regulation constraints, and uncertainties in renewable energy output within grid partitions, making it more consistent with engineering practice and yielding more practical partitioning schemes. Since the objective function includes node load restoration time variables in the recovery process, which makes direct solution difficult, an effective decomposition-based solution strategy is proposed. Specifically, the model is reformulated as a two-level optimization framework: the upper-level model is a robust partitioning optimization problem with given node load restoration times, solved using the constraint generation method (CG); the lower-level model is an approximate recovery optimization model for a given partition scheme, solved using the column and constraint generation method (C&CG). This solution algorithm effectively addresses the two interdependent subproblems of partitioning optimization and system recovery. Case studies and practical system tests verify the effectiveness and superiority of the proposed model and algorithm.