With increasing popularity of media enabled hand-helds and their integration with the in-vehicle entertainment systems, the need for high data-rate services for mobile users on the go is evident. This ever-increasing demand of data is constantly surpassing what cellular networks can economically support. Large-scale Wireless LANs (WLANs) can provide such a service, but they are expensive to deploy and maintain. Open WLAN access-points, on the other hand, need no new deployments, but can offer only opportunistic services, lacking any performance guarantees. In contrast, a carefully planned sparse deployment of roadside WiFi provides an economically scalable infrastructure with quality of service assurance to mobile users. In this paper, we present a new metric, called Contact Opportunity, to closely model the quality of data service that a mobile user might experience when driving through the system. We then present efficient deployment algorithms for minimizing the cost for ensuring a required level of contact opportunity. We further extend this concept and the deployment techniques to a more intuitive metric -- the average throughput -- by taking various dynamic elements into account. Simulations over a real road network and experimental results show that our approach achieves significantly better cost vs. throughput tradeoff in both the worst case and average case compared with some commonly used deployment algorithms.