Service providers seek scalable and cost-effective cloud solutions for hosting their applications. Despite significant advances facilitating cloud services deployment and management, a number of challenges still remain. Service providers are confronted with time-varying workloads, inter-dependencies between components, performance variability of the procured virtual resources, and cost structures that differ from conventional data centers. Moreover, fulfilling service level agreements (SLAs), such as the throughput and response time percentiles, becomes of paramount importance for ensuring business advantages. In this dissertation paper, we explore service provisioning in clouds from multiple points of view. The aim is to best provide service replicas in the form of VMs to various applications, such that their tail throughputs and tail response times, as well as resource utilization, meet the SLAs in the most cost effective manner. In particular, we develop models, algorithms and replication strategies that consider multi-tier services provisioned in the cloud, investigate how a service provider can opportunistically take advantage of observed cloud performance variability and provide means of guaranteeing tail throughput and response times in the face of the aforementioned performance variability. Overall, this dissertation paper provides not only a multi-faceted approach to exploring several crucial aspects of cloud-hosted services, i.e., cost, tail throughput, and tail response times, but our proposed management strategies are also rigorously validated via trace-driven simulations and extensive experiments.