We consider the problem of rate-distortion (RD) optimized media streaming in unstructured peer-to-peer (P2P) overlay networks. We formulate the aforementioned problem as a distributed rate allocation problem, and we solve it by applying classical decomposition techniques so that the network- wide utility of the media distortion is minimized. Information exchange between the peers is employed to ensure updates on the price of the locally calculated rate allocation. Media packets are also piggybacked with RD preambles that contain information regarding their impact on the decoder distortion and their size. The benefit of the aforementioned approach is that peers can convert the calculated optimal rate allocation into simple forwarding or dropping actions allowing thus a lightweight implementation. Our simulation results indicate that significant quality benefits canbe achieved whenthe precise RD characteristics of a media description are taken into account by the streaming algorithm.