Rising provider turnover results in frequently needing to rematch patients with available providers. However, the rematching process is cumbersome for both patients and health systems, resulting in labor-intensive and ad hoc reassignments. We propose a novel patient-provider matching approach to address this issue by offering patients limited provider menus. The goal is to maximize match quality across the system while preserving patient choice. We frame this as a novel variant of assortment optimization, where patient-specific provider menus are offered upfront, and patients respond in a random sequence to make their selections. This hybrid offline-online setting is understudied in previous literature and captures system dynamics across various domains. We first demonstrate that a greedy baseline policy--which offers all providers to all patients--can maximize the match rate but lead to low-quality matches. Based on this, we construct a set of policies and demonstrate that the best policy depends on problem specifics, such as a patient's willingness to match and the ratio of patients to providers. On real-world data, our proposed policy improves average match quality by 13% over a greedy solution by tailoring assortments based on patient characteristics. Our analysis reveals a tradeoff between menu size and system-wide match quality, highlighting the value of balancing patient choice with centralized planning.