Sachverhalt: A. Das basel-städtische Gesetz vom 13. Oktober 1993 betreffend die öffentlichen Ruhetage sowie die Ladenschlusszeiten der Verkaufslokale an Werktagen (Ruhetags- und Ladenschlussgesetz; im Folgenden: RLG/BS) sieht in § 6 (Fassung vom 24. Juni 1998) vor, dass die Verkaufslokale werktags von 1830 Uhr bis 0600 Uhr geschlossen zu halten bzw. an Vorabenden der öffentlichen Ruhetage um 1700 Uhr zu schliessen sind. Sodann bestimmen § 11 Abs. 2 und 3 RLG/BS (letztgenannter Absatz in der Fassung vom 24. Juni 1998): "2 Der Regierungsrat kann auf dem Verordnungswege Ausnahmebestimmungen festlegen für Messen und Märkte, für die Fasnacht, sowie für besondere Anlässe oder bei ausserordentlichen örtlichen Verhältnissen. 3 Ferner haben für das Stadtgebiet der Regierungsrat und für die Landgemeinden der jeweilige Gemeinderat folgende Befugnisse: - die Öffnungszeiten der Verkaufslokale von Montag bis und mit Freitag bis längstens 20.00 Uhr und an einem dieser Tage bis längstens 21.00 Uhr generell zu erweitern, sofern die beteiligten Arbeitgeber- und Arbeitnehmerorganisationen mit dieser Änderung einverstanden sind; - [...]." B. Am 5. August 2003 beschloss der Regierungsrat des Kantons Basel-Stadt, die Verordnung vom 7. Dezember 1993 zum Gesetz betreffend die öffentlichen Ruhetage sowie die Ladenschlusszeiten der Verkaufslokale an Werktagen (Ruhetags- und Ladenschlussverordnung; im Folgenden: RLV/BS) wie folgt zu ändern (effektiv geänderte Passagen in Kursivschrift): "§ 7 Abs. 1 enthält folgende neue Fassung: § 7. An Werktagen, die keine öffentlichen Ruhetage im Sinne von § 3 des Gesetzes sind und auch nicht Vortage vor solchen Ruhetagen, dürfen gemäss § 11 Abs. 3 des Gesetzes, aufgrund des Gesamtarbeitsvertrages für den Abendverkauf im Kanton Basel-Stadt vom 1. Mai 2002 und in Beachtung dieses Gesamtarbeitsvertrages, die Verkaufslokale ausserhalb der beiden Landgemeinden wie folgt geöffnet haben: a) an Donnerstagen bis längstens 21.00 Uhr; b) von Montag bis Mittwoch und freitags bis längstens 19.00 Uhr.] § 7a enthält folgende neue Fassung: § 7a. Das Kantonale Amt für Industrie, Gewerbe und Arbeit kann bei ausserordentlichen örtlichen Verhältnissen im Sinne von § 11 Abs. 2 des Gesetzes an Werktagen, die keine öffentlichen Ruhetage im Sinne von § 3 des Gesetzes und auch nicht Vortage vor solchen Ruhetagen sind, bewilligen, dass die Verkaufslokale von Montag bis Mittwoch und am Freitag bis 20.00 Uhr, am Donnerstag bis 21.00 Uhr geöffnet bleiben dürfen, sofern: a) Die Verkaufslokalitäten ausserhalb von Wohnquartieren sind und keine Beeinträchtigung des Wohnens und der Erholung der Bevölkerung stattfindet und b) die betroffenen Lokalitäten eine räumlich abgrenzbare Einheit, bzw. Zentrum bilden und c) die betroffenen Zentren in direkter Konkurrenz zu solchen stehen, welche diesem Gesetz nicht unterstehen und d) dem Verkaufspersonal mindestens die gleichen Bedingungen analog dem Gesamtarbeitsvertrag für den Abendverkauf im Kanton Basel-Stadt vom 1. Mai 2002 gewährt werden. Es wird folgender § 7b neu eingefügt: Bewilligungsverfahren bei ausserordentlichen örtlichen Verhältnissen § 7b. [...]" Die geänderten Verordnungsbestimmungen unterscheiden sich inhaltlich in zweierlei Hinsicht von ihrer bisherigen Fassung: Einerseits sieht die Regelung betreffend die verlängerten Ladenöffnungszeiten bei ausserordentlichen örtlichen Verhältnissen neu ein Bewilligungsverfahren vor (§ 7a Ingress sowie neu eingefügter § 7b), wogegen bisher ein behördlicher Entscheid über das Vorliegen der Voraussetzungen nur "im Zweifel" erforderlich war. Andererseits wurden die Voraussetzungen, um von den verlängerten Öffnungszeiten profitieren zu können, generell in der Weise angepasst, dass nunmehr (in § 7 Abs. 1 Ingress bzw. in § 7a lit. d RLV/BS) auf den "Gesamtarbeitsvertrag für den Abendverkauf im Kanton Basel-Stadt vom 1. Mai 2002" Bezug genommen wird; bisher hatten die Bestimmungen auf eine von den Sozialpartnern am 18. März 1998 abgeschlossene "Vereinbarung über die Ausweitung der Ladenöffnungszeiten am Abend" verwiesen. Nicht Gegenstand der Änderungsvorlage bildete die zeitliche Festlegung der verlängerten Öffnungszeiten in lit. a und b von § 7 Abs. 1 RLV/BS (oben in Klammern wiedergegeben), welche demzufolge unverändert bleiben sollten. Der Regierungsrat setzte diese Verordnungsänderung auf den 1. November 2003 in Kraft. C. Mit Eingabe vom 26. September 2003 erheben der Gewerbeverband Basel-Stadt, der Verein Pro Innenstadt sowie die X._ AG, alle mit Sitz in Basel, beim Bundesgericht staatsrechtliche Beschwerde, mit der sie die Aufhebung der am 5. August 2003 beschlossenen Änderung von § 7 Abs. 1 und § 7a lit. d RLV/BS beantragen. Sie beanstanden, dass die in diesen Bestimmungen vorgesehenen verlängerten Öffnungszeiten von der Einhaltung der Bedingungen eines - von ihnen als inakzeptabel erachteten - Gesamtarbeitsvertrages abhängig gemacht werden, und erblicken hierin einen Verstoss gegen den Grundsatz der derogatorischen Kraft des Bundesrechts (Art. 49 Abs. 1 BV) sowie eine Verletzung der Wirtschaftsfreiheit (Art. 27 BV). D. Dem von den Beschwerdeführern gestellten Gesuch um aufschiebende Wirkung wurde mit Verfügung des Präsidenten der II. öffentlichrechtlichen Abteilung vom 21. Oktober 2003 entsprochen. E. Der Vorsteher des Wirtschafts- und Sozialdepartements (im Auftrag des Regierungsrates) des Kantons Basel-Stadt beantragt mit Vernehmlassung vom 13. Januar 2003 (recte: 2004), die Beschwerde abzuweisen, soweit darauf einzutreten sei. In ihrer am 27. Februar 2004 eingereichten Ergänzung zur Beschwerde (Art. 93 Abs. 2 OG) halten die Beschwerdeführer an ihren Rechtsbegehren fest. Ebenso bestätigt der Vorsteher des Wirtschafts- und Sozialdepartements mit Vernehmlassung zur Beschwerdeergänzung vom 1. April 2004 die seitens des Regierungsrates gestellten Anträge.