Faits : A. Les époux A.A._ et B.A._ sont propriétaires des biens-fonds n° 121 et 126 de la Commune de Veytaux, en bordure d'une route cantonale. La société D._ Sàrl y exploite le restaurant du même nom. Sur la parcelle voisine au sud n° 118 se trouve un bâtiment abritant l'établissement public "E._", exploité par C._ Sàrl. Le restaurant "D._" bénéficie d'une terrasse, située sur le trottoir, soit sur le domaine public. Sur le domaine public également, au droit du bien-fonds n° 121, deux regards en fonte recouvrent un séparateur et un décanteur de graisses, installation destinée à collecter la graisse contenue dans les eaux usées provenant des cuisines du restaurant voisin "E._", avant que celles-ci ne s'écoulent dans les égouts publics. Le 17 mai 2011, les époux A._ ont requis la municipalité d'ordonner la suppression du séparateur-décanteur, invoquant le fait que cette installation avait été réalisée sans permis de construire. B. Le 6 mars 2012, la municipalité de Veytaux a rendu une décision refusant d'ordonner la suppression du séparateur-décanteur, retenant en particulier que cette installation avait été dûment autorisée par un permis de construire du 29 septembre 1986 ainsi que par un permis délivré par le Service cantonal des routes le 3 février 1987. Les époux A._ ont recouru contre cette décision devant la Cour de droit administratif et public du Tribunal cantonal. Au cours de l'instruction menée par la cour cantonale, celle-ci a notamment procédé à une visite des lieux et mandaté un ingénieur pour réaliser une expertise sur les éventuelles nuisances olfactives en cause. Le recours a été rejeté par arrêt du 22 décembre 2014. Les premiers juges ont notamment considéré que la modification de l'emplacement du séparateur-décanteur par rapport aux plans approuvés avec le permis de construire du 29 septembre 1986 aurait dû faire l'objet d'une enquête publique. Toutefois, au vu notamment de l'absence de préjudice causé au voisinage, il ne se justifiait pas pour autant d'ordonner une remise en état ou une suppression de l'installation. C. Agissant par la voie du recours en matière de droit public, A.A._ et B.A._ demandent au Tribunal fédéral de réformer l'arrêt cantonal en ce sens que la commune doit ordonner au propriétaire de la parcelle n° 118 de supprimer le séparateur-décanteur de graisses et le dépotoir de l'établissement public qu'il exploite du trottoir et de l'emplacement au droit de la parcelle n° 121. Subsidiairement, les recourants concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'instance précédente pour nouvelle décision. La cour cantonale conclut au rejet du recours en se référant aux considérants de l'arrêt attaqué. La commune et l'intimée C._ Sàrl se déterminent et concluent au rejet du recours. La Direction générale de l'environnement du canton de Vaud se réfère aux déterminations qu'elle a déposées dans le cadre de la procédure cantonale. La Direction générale de la mobilité et des routes du canton de Vaud et le Service intercommunal de gestion ne se déterminent pas. Consulté, l'Office fédéral de l'environnement renonce à prendre position dans cette affaire. Les recourants répliquent et persistent dans leurs conclusions. Par ordonnance du 24 mars 2015, le Président de la Ire Cour de droit public a rejeté la demande d'effet suspensif présentée par les recourants.