Sachverhalt: A. A.a. Der Kanton Basel-Stadt plant die umfassende Sanierung der Verkehrsachse Äussere Baselstrasse zwischen Basel und Riehen. Für die Arbeiten an einem Teilstück (Lose 2 und 3) soll auf einer Grünfläche zwischen den beiden Strässchen Bäumlihofwegli und Im Hirshalm ein zentraler Installationsplatz erstellt und während mehreren Jahren betrieben werden; gerechnet wird mit ca. 66 Fahrten täglich, zu einem namhaften Teil auch nachts. A.b. A. und B. C._ wohnen an der Ecke Äussere Baselstrasse/Im Hirshalm, d.h. direkt gegenüber der Einfahrt zum geplanten Installationsplatz. Ihre - gegen den Installationsplatz gerichtete - Einsprache gegen die Pläne zur Sanierung der Äusseren Baselstrasse hat der Regierungsrat des Kantons Basel-Stadt mit dem Plangenehmigungsentscheid vom 8./9. Dezember 2015 abgewiesen. B. Dagegen erhoben A. und B. C._ am 18. Dezember 2015 beim Appellationsgericht Basel-Stadt Rekurs und ersuchten dabei um aufschiebende Wirkung. Mit Verfügung vom 22. Dezember 2015 gab der Instruktionsrichter diesem Begehren provisorisch statt. In einer weiteren Zwischenverfügung vom 23. Februar 2016 entzog er auf Antrag des Regierungsrats dem Rekurs die aufschiebende Wirkung wieder. C. Gegen diesen Entscheid führen A. und B. C._ mit Eingabe vom 10. März 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen dessen Aufhebung und die Bestätigung bzw. Wiederherstellung der aufschiebenden Wirkung ihres Rekurses. Sodann stellen sie den Prozessantrag, ihrer Beschwerde sei die aufschiebende Wirkung zu gewähren. Das Bau- und Verkehrsdepartement des Kantons Basel-Stadt beantragt, auf die Beschwerde sei nicht einzutreten, eventuell sei sie abzuweisen. Der Präsident des Appellationsgerichts beantragt die Abweisung der Beschwerde. Die Beschwerdeführenden haben am 15. April 2016 repliziert. D. Mit Verfügung vom 31. März 2016 wies der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts das Gesuch um Erteilung der aufschiebenden Wirkung ab.