Faits: A. C._ est propriétaire de la parcelle n° 568 du registre foncier de la Tour-de-Peilz (VD), sur laquelle est bâtie une maison d'habitation agrémentée d'une piscine. Une haie séparait ce bien-fonds de la parcelle voisine n° 569, propriété de A._ et B._ (ci-après: les époux A._). Désireux de remplacer cette haie par une palissade, C._ a contacté le Service de l'urbanisme et des travaux publics de la Tour-de-Peilz (devenu "Direction de l'urbanisme et des travaux publics"; ci-après: le service de l'urbanisme). La réponse qu'il a reçue laissant croire que ce projet pouvait être réalisé sans mise à l'enquête publique, C._ a arraché la haie et réalisé la palissade. Interpellé par les époux A._, le Service cantonal de l'aménagement du territoire a estimé que l'ouvrage en question aurait dû faire l'objet d'une enquête publique. Se fondant sur cet avis, la Municipalité de la Tour-de-Peilz (ci-après: la municipalité) a, par courrier du 3 septembre 2002, requis C._ de régulariser la construction litigieuse par le biais d'une mise à l'enquête publique et lui a imparti un délai pour déposer un dossier à cette fin. Par décision du 14 novembre 2002, la municipalité a confirmé l'exigence d'une mise à l'enquête publique. Par arrêt du 13 mai 2006, le Tribunal administratif du canton de Vaud a rejeté le recours formé par C._ contre cette décision. La Cour de céans a confirmé cet arrêt le 18 octobre 2006 (arrêt 1P.373/2006). B. C._ a alors déposé une demande de permis de construire. Il ressort des plans annexés à la demande que la palissade a une longueur de 22,75 m et une hauteur maximale de 2,80 m à compter du remblai aménagé sur la parcelle du constructeur, voire de 3,60 m à compter du terrain des époux A._. Mis à l'enquête publique du 21 mars au 19 avril 2007, le projet a suscité diverses oppositions, dont celle des époux A._. Par décision du 10 juillet 2007, la municipalité a écarté les oppositions et délivré le permis de construire. Les époux A._ ont recouru contre cette décision auprès du Tribunal administratif du canton de Vaud (devenu la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud; ci-après: le Tribunal cantonal), qui a rejeté ce recours par arrêt du 16 décembre 2008. En substance, cette autorité a considéré que le dossier de mise à l'enquête était complet, que l'arrachage de la haie n'était pas soumis à autorisation, que les dimensions de la palissade étaient conformes à l'art. 39 du règlement d'application de la loi cantonale sur l'aménagement du territoire et les constructions (RATC; RSV 700.11.1) et à l'art. 82 du règlement sur le plan d'extension et la police des constructions de la commune de la Tour-de-Peilz du 5 juillet 1972 (ci-après: le règlement communal). Procédant à une pesée des intérêts en présence, le Tribunal cantonal a en outre considéré que la palissade litigieuse était "supportable sans sacrifice excessif" de la part des voisins, de sorte que la condition de l'art. 39 al. 4 RATC était respectée. C. Agissant seuls, A._ et B._ forment un recours au Tribunal fédéral à l'encontre de cet arrêt. Ils concluent à l'annulation de l'arrêt attaqué et de la décision de la municipalité du 10 juillet 2007, ainsi qu'au renvoi de la cause à l'autorité inférieure pour qu'elle impose à la municipalité de se prononcer également sur l'arrachage de la haie, subsidiairement sur la hauteur de l'ouvrage litigieux. Ils se plaignent en substance d'une application arbitraire (art. 9 Cst.) des règles sur la hauteur et sur le préjudice, ainsi que d'une violation de leur droit d'être entendus (art. 29 al. 2 Cst.) en raison d'un défaut de motivation. C._ et la Municipalité de la Tour-de-Peilz se sont déterminés; ils concluent au rejet du recours, dans la mesure de sa recevabilité. Le Tribunal cantonal se réfère aux considérants de son arrêt. A._ et B._ ont présenté des observations complémentaires. 