Because conventional computational approaches falter under heavily constrained and nonlinear conditions, properly setting protective distribution relays remains an arduous task. While the metaheuristic algorithms have been applied to this problem, existing approaches typically optimize only time and current settings while assuming fixed relay characteristics, limiting the achievable coordination performance. This paper addresses this gap by proposing a unified Gravitational Search Algorithm (GSA) framework that simultaneously optimizes time multiplier settings, current settings, and relay characteristic selection from eight standard curves. By leveraging a combination of MATLAB for optimization and DIgSILENT for fault current estimation, this study evaluates its approach. The effectiveness of the technique is demonstrated through testing on both 30-bus and 9-bus distribution systems, where its performance is benchmarked against Informative Differential Evolution and Particle Swarm Optimization. Results demonstrate that the GSA-based approach achieves superior convergence and lower objective function values, with statistical analysis confirming its robustness and effectiveness in reducing relay operating times compared to the existing methods.