Faits: A. A._ et B._ sont propriétaires de la parcelle n° 12'592 du registre foncier de la commune de Montreux. Cette parcelle est située au coeur d'un coteau pentu originairement viticole dominant le centre de la ville de Montreux, dans un secteur résidentiel moyennement bâti. Le 24 novembre 2008, les prénommés ont obtenu un permis de construire une villa individuelle de 343 m2 sur trois niveaux avec deux dépendances souterraines dont un garage. Le permis de construire précisait cependant que: "42. Compte tenu du décor paysager caractéristique d'anciens parchets de vigne, les plantations arbustives feront l'objet d'une concertation avec les services de l'urbanisme et de voirie espaces verts. D'autre part conformément au plan des aménagements extérieurs, la partie inférieure de la parcelle sera maintenue en vigne. 43. Conformément à l'arrêté du Conseil d'Etat du 7 juillet 1999 concernant la lutte contre le feu bactérien et prophylaxie, nous interdisons la plantation de végétaux jugés "très sensibles" au feu bactérien, selon la circulaire fédérale du 3 décembre 1997 [...]. D'autre part, les plans hôtes du feu bactérien sont à limiter, selon l'annexe 3 de l'ordonnance fédérale du 28 avril 1982. Il s'agit d'exiger de votre fournisseur toutes les garanties quant à la provenance des plantes achetées, en particulier [...]". B. Par courrier du 6 janvier 2009, le chef du Service de l'urbanisme de la commune de Montreux a signalé aux constructeurs que le mur de soutènement de la rampe d'accès n'apparaissait pas sur les documents soumis à l'enquête publique et ne saurait dès lors être autorisé. Après remise de nouveaux plans par les constructeurs, la Direction du développement urbain et du territoire (ci-après: la Direction) a autorisé la reprise des travaux, tout en précisant qu'un plan dressant la nomenclature des essences devait être produit le moment venu au Service de l'urbanisme pour la plantation de végétation arbustive devant l'ouvrage de soutènement, par lettre du 30 janvier 2009. La Direction a rappelé cette exigence, par courrier du 23 mars 2009. Le 25 juin 2009, le Service de l'urbanisme a constaté que la plantation d'une trentaine de cyprès de 6 à 7 mètres de hauteur était en cours à l'aplomb de la rampe d'accès. Le lendemain, la Municipalité de Montreux (ci-après: la Municipalité) a ordonné l'arrêt immédiat des travaux de plantation, relevant que ceux-ci n'étaient conformes ni au permis de construire délivré, ni aux accords survenus ultérieurement au sujet des aménagements extérieurs et qu'ils portaient atteinte aux caractéristiques du site. Elle a ensuite soumis la question au "comité d'expert" prévu par le nouveau règlement communal qui a formulé un avis négatif sur la plantation de cyprès dans le cadre paysager viticole. Une telle plantation était incongrue en tant qu'elle introduisait un cliché étranger et anecdotique dans le site. L'alignement de ces arbres fastigiés dramatisait encore la perception visuelle du mur, déjà trop haut. Par décision du 30 juillet 2009, la Municipalité a ordonné l'enlèvement des cyprès déjà plantés. A._ et B._ ont recouru contre cette décision auprès de la Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après: le Tribunal cantonal). Celle-ci a procédé à une inspection locale le 26 février 2010 en présence des parties. Par arrêt du 28 avril 2010, elle a admis le recours en tant qu'il concerne la modification de l'ouvrage soutenant la terrasse intermédiaire et l'a rejeté pour le surplus. Elle a considéré en substance que la Municipalité n'avait pas abusé de son large pouvoir d'appréciation en refusant d'autoriser a posteriori la plantation des cyprès. L'ordre de remise en état respectait en outre le principe de la proportionnalité. C. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral de réformer, cas échéant d'annuler cet arrêt, en ce sens que la décision de la Municipalité du 30 juillet 2009 ordonnant l'enlèvement des cyprès déjà plantés est annulée. Ils se plaignent notamment de violations de la garantie de la propriété, du principe de la proportionnalité et de l'interdiction d'arbitraire. Le Tribunal cantonal conclut au rejet du recours en se référant aux considérants de l'arrêt attaqué. La Municipalité de Montreux renonce à se déterminer et s'en remet à justice. 