Spatial Crowdsourcing (SC) has become a popular paradigm for executing spatiotemporal tasks, such as urban sensing, ride-hailing, and last-mile delivery. In many of these service applications, it is common for workers to undertake multiple tasks simultaneously, as this allows them to efficiently complete tasks with a convenient route. In multi-task SC, location privacy, movement cost, and service quality constitute the three most critical factors. However, the inherent contradictions among these factors pose significant challenges in simultaneously ensuring them all, and to date, no existing work has addressed all three factors concurrently. To fill the research gap, in this paper, we propose a Privacy-Preserving, Cost-Aware, and Quality-Enabled Service Planning (PCQ-SP) scheme for multi-task SC. First, we introduce a secure distance acquisition method with additive homomorphic encryption and garbled circuits, which enables the calculation of distances between workers and tasks while preserving both their location privacy. Second, we design a Thompson Sampling-based quality evaluation method to assess each worker’s service quality by balancing exploration and exploitation. Third, we propose a minimum-cost flow-driven service planning method to derive the optimized service plans, which aims for high quality and low cost while preserving location privacy. To our knowledge, our PCQ-SP scheme is the first to simultaneously consider location privacy, movement cost, and service quality in SC systems. Extensive evaluations demonstrate the effectiveness of our PCQ-SP scheme in enhancing service quality, reducing movement costs, and ensuring location privacy.