The presence of millions of interconnected personal computing devices has given rise to a new class of decentralized networking applications, which are loosely labeled as peer-to-peer (P2P) applications. These P2P applications leverage resources such as processing cycles, storage, content, and network bandwidth available to the user devices, which are also known as peers. A number of current systems - SETI@home, Napster, BitTorrent, and Pastry - are examples of these emerging P2P systems. To fully realize the potential of the peer-to-peer technology, there is a need to define and provide a set of core competencies, serving as the basic services upon which various peer-to-peer applications can be built on. Among these core competencies, this dissertation focuses on two fundamental services, which are search and delivery. In the first part of the dissertation, delivery techniques to support video-on-demand services in wireline and wireless P2P networks are investigated. Video services are considered due to two reasons. First, video services are the pivotal basis for many other multimedia applications. Second, it is challenging to provide on-demand video services due to asynchronous playback progresses at peers. The proposed techniques enable efficient video sharing between peers with asynchronous playback progresses, and maximize peer bandwidth utilization. In the second part of the dissertation, the problem of supporting continuous moving range queries in wireless mobile peer-to-peer networks is studied. Continuous moving range queries have a number of applications when a moving object wants to monitor its surrounding environment for a period of time. When a fixed network infrastructure is not available, wireless mobile peer-to-peer networks become a viable option to support the continuous query system. The proposed distributed solution ensures the accuracy of the query results under realistic assumptions, and incurs much less overhead than alternative solutions.