Vehicle rental providers offer differentiated services to reserve and walk-in customers. In this research, we study one such service differentiation strategy, a vehicle threshold policy, which is to hold vehicles for reserve class customers in anticipation of their future arrivals. To consider the impact that vehicle threshold policies have on reserve and walk-in customer waiting times, we model a rental depot as a multi-class non-work-conserving semi-open queue with stochastic inputs. For exponential and deterministic service time distributions, we identify the optimal threshold quantity for stationary customer arrivals using closed-form expressions for the expected waiting times of both customer classes. For non-stationary customer arrivals, we develop different threshold policies and analyze their performance using a detailed simulation model. Through numerical testing, we provide insights into recommended threshold policies that can be applied to improve the profitability of a rental provider.