Titanium alloy (Ti-6Al-4V) is a difficult-to-machine material, known for its excellent physical and chemical properties. However, traditional machining methods incur high tool wear costs when processing this material. The near-dry electrical discharge milling (N-EDM) method, which removes excess material via electroerosion, mitigates the impact of titanium alloy’s hardness and strength, enabling effective material cutting. To enhance machining efficiency and surface quality, this study employs a simulation model of the inter-electrode flow field, combined with experimental data, to investigate the effect of milling thickness on key machining parameters and determine the optimal thickness. Subsequently, a four-factor, three-level (L27(43)) orthogonal experiment was designed, with current, duty cycle, gas pressure, and atomization rate as input parameters. Material removal rate (MRR), relative electrode wear ratio (REWR), width of cut (WOC), and roughness average (Ra) were selected as primary optimization indicators. Based on the orthogonal experiment results, analysis of variance (ANOVA) was conducted to examine the influence of the input parameters on the various process indicators and determine the optimal single-objective processing parameters. Using Grey Relational Analysis (GRA), the multi-objective optimal machining parameters were identified as: 2 A current, 40% duty cycle, 0.2 MPa gas pressure, and 20 ml/min atomization rate. These parameters significantly enhance both processing efficiency and surface quality.