Faits: A. A.a. A._ et la société B._ Sàrl ont requis le 19 septembre 2012 une licence pour ouvrir à Lausanne une discothèque à l'enseigne " C._ ", située dans le quartier historique de la Cité, établissement qui était exploité jusqu'au 31 août 2012 à l'enseigne " D._ ". Les intéressés sont par ailleurs au bénéfice d'une licence pour le restaurant " E._ ", séparé de la discothèque par une terrasse. A.b. Par décision du 19 octobre 2012, la Municipalité de Lausanne (ci-après: la Municipalité) a subordonné l'octroi de la licence requise à plusieurs conditions, notamment: de fixer, en application des art. 77 RPGA et 9 RME, l'horaire de la discothèque exploitée à l'enseigne " C._ " par B._ SARL (exploitant) et par M. A._ (exerçant) de la manière suivante: du dimanche au mercredi de 17h00 à 01h00 le jeudi de 17h00 à 02h00 les vendredis et samedis de 17h00 à 03h00, et d'exclure toute possibilité de prolongation de l'horaire au sens de l'art. 6 RME. Le 2 novembre 2012, la Police cantonale du commerce, rattachée au Service de la promotion économique et du commerce (ci-après: Le Service cantonal) a délivré aux intéressés une licence pour l'exploitation de la discothèque " C._ ", qui reprend les horaires d'ouverture tels qu'ils résultent de la décision du 19 octobre 2012 de la Municipalité, sans prolongation possible. A.c. Le 21 novembre 2012, A._ et B._ Sàrl ont recouru contre la décision de la Municipalité du 19 octobre 2012 et celle du Service cantonal du 2 novembre 2012 auprès de la Cour de droit administratif et public du Tribunal cantonal (ci-après: le Tribunal cantonal). Ils ont conclu en particulier à la réforme des décisions attaquées en ce sens que l'horaire d'ouverture soit fixé à 04h00 chaque jour, avec possibilité de fermeture à 05h00 moyennant le paiement d'une taxe. Lors de l'inspection locale mise en oeuvre au cours de l'instruction par le Tribunal cantonal, les représentants de la Municipalité ont indiqué vouloir appliquer les mêmes horaires d'ouverture que ceux qui étaient imposés à la discothèque « C._ », sans prolongation possible, à tous les établissements de nuit des secteurs à habitat prépondérant de la ville lors de chaque changement nécessitant la délivrance d'une nouvelle licence, en particulier lors d'un changement de titulaire. B. Par arrêt du 26 août 2013, le Tribunal cantonal a rejeté le recours de A._ et de B._ Sàrl et confirmé la décision de la Municipalité du 19 octobre 2012 et celle du Service cantonal du 2 novembre 2012. C. Contre l'arrêt du 26 août 2006, A._ et B._ Sàrl forment un recours en matière de droit public devant le Tribunal fédéral. Ils concluent principalement, sous suite de frais et dépens, à la réforme de la décision du 19 octobre 2012 en ce sens que les horaires d'ouverture de la discothèque " C._ " soient fixés à 03h00 chaque jour, avec possibilité de fermeture à 05h00, ladite décision étant maintenue pour le surplus et la licence délivrée par le Service cantonal étant modifiée en conséquence. Subsidiairement, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause à l'autorité cantonale et communale pour nouvelle décision dans le sens des considérants. Ils concluent dans les deux cas à l'allocation de dépens de première instance. La Municipalité de Lausanne conclut au rejet du recours dans la mesure de sa recevabilité. Le Service cantonal conclut au rejet du recours. Le Tribunal cantonal se réfère aux considérants de l'arrêt attaqué.