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 (<ref-law>) sowie eine Verletzung der Wirtschaftsfreiheit (<ref-law>).
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.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Nach Art. 84 Abs. 1 lit. a OG kann gegen kantonale Erlasse wegen Verletzung verfassungsmässiger Rechte staatsrechtliche Beschwerde geführt werden. Bei der angefochtenen Verordnungsänderung (§ 7 Abs. 1 sowie § 7a lit. d RLV/BS in der Fassung vom 5. August 2003) handelt es sich um einen letztinstanzlichen kantonalen Hoheitsakt, gegen den als eidgenössisches Rechtsmittel einzig die staatsrechtliche Beschwerde zur Verfügung steht (Art. 84 Abs. 2 und Art. 86 Abs. 1 OG).
1. 1.1 Nach Art. 84 Abs. 1 lit. a OG kann gegen kantonale Erlasse wegen Verletzung verfassungsmässiger Rechte staatsrechtliche Beschwerde geführt werden. Bei der angefochtenen Verordnungsänderung (§ 7 Abs. 1 sowie § 7a lit. d RLV/BS in der Fassung vom 5. August 2003) handelt es sich um einen letztinstanzlichen kantonalen Hoheitsakt, gegen den als eidgenössisches Rechtsmittel einzig die staatsrechtliche Beschwerde zur Verfügung steht (Art. 84 Abs. 2 und Art. 86 Abs. 1 OG).
1.2 1.2.1 Zur staatsrechtlichen Beschwerde gegen einen kantonalen Erlass auf dem Wege der abstrakten Normenkontrolle ist legitimiert (Art. 88 OG), wer durch die angefochtenen Bestimmungen unmittelbar oder zumindest virtuell, d.h. mit einer minimalen Wahrscheinlichkeit früher oder später einmal, in seinen rechtlich geschützten Interessen betroffen ist (<ref-ruling> E. 1.2.1. S. 29 f., 82 E. 1.3 S. 85; <ref-ruling> E. 1b/aa S. 75, 173 E. 1b S. 174; <ref-ruling> E. 1c S. 442, je mit Hinweisen). Das Anrufen bloss tatsächlicher oder allgemeiner öffentlicher Interessen genügt zur Begründung der Legitimation nicht; auch zur Anfechtung von Erlassen ist ein drohender Eingriff in rechtlich geschützte eigene Interessen erforderlich (<ref-ruling> E. 5b S. 42 f.; <ref-ruling> E. 2b S. 45 f. mit weiteren Hinweisen).
Im selben Rahmen kann auch ein als juristische Person konstituierter Verband die Verletzung von verfassungsmässigen Rechten seiner Mitglieder geltend machen, soweit er nach den Statuten die entsprechenden Interessen zu wahren hat und die Mehrheit oder zumindest eine Grosszahl der Mitglieder durch die angefochtene Regelung direkt oder virtuell betroffen sind (sog. "egoistische Verbandsbeschwerde": <ref-ruling> E. 1.2.1 S. 30, 82 E. 1.3 S. 85; <ref-ruling> E. 1b/aa S. 75, je mit Hinweisen).
1.2.2 Die beschwerdeführenden, als Vereine im Sinne von <ref-law> mit Sitz in Basel konstituierten beiden Verbände (Beschwerdeführer 1 und 2) vertreten eine Grosszahl von Mitgliedern, denen als Inhabern von Verkaufsgeschäften die Inanspruchnahme der verlängerten Öffnungszeiten verwehrt ist, falls sie die Bedingungen des Gesamtarbeitsvertrages für den Abendverkauf vom 1. Mai 2002 (im Folgenden: Gesamtarbeitsvertrag 2002), dem sie nicht angeschlossen sind, nicht befolgen. Sie werden damit in ihrer durch <ref-law> geschützten wirtschaftlichen Tätigkeit beeinträchtigt. Die Legitimation der nicht dem genannten Gesamtarbeitsvertrag angeschlossenen Verkaufsbetriebe ist nicht nur in Bezug auf § 7 Abs. 1 RLV/BS (generelle Verlängerung der Öffnungszeiten, Abendverkauf), sondern auch in Bezug auf § 7a RLV/BS (zusätzliche Verlängerung bei ausserordentlichen örtlichen Verhältnissen) zu bejahen, genügt doch im Rahmen einer abstrakten Normenkontrolle bereits die Möglichkeit, dass der einzelne Ladeninhaber als im Kanton Basel-Stadt niedergelassener Gewerbetreibender - sei es aufgrund seines jetzigen Betriebsstandortes, sei es durch Verlegung seines Betriebes oder durch Eröffnung eines zusätzlichen Betriebes - eines Tages in die Lage kommen könnte, die für ausserordentliche örtliche Verhältnisse vorgesehene Sonderregelung zu beanspruchen. Die erforderliche unmittelbare oder virtuelle Betroffenheit in rechtlich geschützten Interessen erscheint jedenfalls für eine Grosszahl der Verbandsmitglieder gegeben, womit die Legitimation auch den beiden Verbänden selber zusteht, zumal die Wahrung dieser Interessen zu deren statutenmässigen Aufgaben gehört. Ob der Beschwerdeführer 1, wie in der Beschwerde geltend gemacht, als tariffähiger Arbeitgeberverband im Sinne von <ref-law> durch die streitigen Bestimmungen auch in seiner eigenen Rechtsstellung (Beeinträchtigung der Freiheit zum Abschluss von Gesamtarbeitsverträgen) betroffen und unter diesem Titel selbständig zur staatsrechtlichen Beschwerde legitimiert wäre, kann, da auf seine Beschwerde ohnehin einzutreten ist, offen bleiben. Die Beschwerdeführerin 3, welche im Stadtzentrum von Basel eine Buchhandlung betreibt, ist zwar am Gesamtarbeitsvertrag für den Buchhandel der deutschsprachigen Schweiz, nicht jedoch am für die Arbeitnehmer vorteilhafteren Gesamtarbeitsvertrag 2002 beteiligt, und kann demzufolge von den verlängerten Ladenöffnungszeiten gemäss § 7 Abs. 1 RLV/BS nicht profitieren, weshalb sie ebenfalls als zur staatsrechtlichen Beschwerde legitimiert erscheint.
1.2.3 Seitens des Kantons wird das Rechtsschutzinteresse der Beschwerdeführer in Frage gestellt mit dem Hinweis, dass sie ungeachtet des Wortlautes der angefochtenen Verordnungsbestimmungen aufgrund bundesrechtskonformer Auslegung derselben faktisch ebenfalls in den Genuss der verlängerten Öffnungszeiten gelangten und dass die Beschwerdeführer bei Aufhebung dieser Bestimmungen sich wieder an die im Gesetz vorgesehenen kürzeren ordentlichen Öffnungszeiten zu halten hätten. Dass der Kanton heute bei der Anwendung der streitigen Bestimmungen den bundesrechtlichen Vorgaben Rechnung zu tragen versucht, ändert nichts an der Befugnis der Beschwerdeführer, die Verfassungs- und Bundesrechtskonformität dieser in ihre Rechtsstellung eingreifenden neuen Verordnungsvorschriften überprüfen zu lassen, unabhängig davon, ob und wieweit sie durch die Ordnung, welche bei Aufhebung der beanstandeten Vorschriften allenfalls Platz greifen könnte, schlechter gestellt wären als nach der gegenwärtigen kantonalen Praxis. Das muss vorliegend umso mehr gelten, als auch die Verfassungsmässigkeit der sowohl der bisherigen wie der neuen Verordnungsregelung zugrunde liegenden Gesetzesbestimmung (§ 11 Abs. 3 RLG/BS) bestritten wird und vorfrageweise ebenfalls zu prüfen ist. Im Übrigen übersieht der Kanton, dass die tatsächliche Auslegung, welche die angefochtenen Bestimmungen in der bisherigen Behördenpraxis erfahren hat, für die verfassungsrechtliche Beurteilung nicht massgebend sein kann, wenn sie mit Wortlaut und Sinn der Norm nicht vereinbar ist; eine Norm ist aufzuheben, wenn sie einer verfassungskonformen Auslegung vertretbarerweise nicht zugänglich ist (vgl. <ref-ruling> E. 2.1 S. 31 f., 82 E. 2.1 S. 86; <ref-ruling> E. 3.2 S. 15; <ref-ruling> E. 3.1 S. 334 f. mit Hinweisen).
1.3 Die angefochtene Verordnungsänderung vom 5. August 2003 wurde am 30. August 2003 unter Festlegung des Zeitpunktes ihres Inkrafttretens im amtlichen Publikationsorgan veröffentlicht (Kantonsblatt Basel-Stadt, 2003/206 Jg., Nr. 65, S. 1224 f.). Die vorliegende Beschwerde vom 26. September 2003 wurde damit rechtzeitig erhoben (Art. 89 Abs. 1 OG).
1.4 Wird ein Erlass nur teilweise revidiert, so können mit staatsrechtlicher Beschwerde grundsätzlich nur diejenigen Bestimmungen im Rahmen der abstrakten Normenkontrolle angefochten werden, die bei der Revision geändert worden sind. Für Normen, die unverändert bleiben oder ohne Änderung aus der bisherigen Regelung übernommen werden, ist die Beschwerdefrist abgelaufen; eine Anfechtung kommt nur unter besonderen Voraussetzungen in Frage (vgl. <ref-ruling> E. 1b/aa S. 224 f. mit Hinweisen). Die beiden angefochtenen Verordnungsbestimmungen (§ 7 Abs. 1 sowie § 7a lit. d RLV/BS in der Fassung vom 5. August 2003) sehen zwar die erweiterten Öffnungszeiten unverändert im bisherigen Umfange vor, nehmen jedoch nunmehr Bezug auf einen neu abgeschlossenen Gesamtarbeitsvertrag mit (gegenüber der früheren sozialpartnerschaftlichen Vereinbarung von 1998) umfassenderer Regelung der Arbeitsbedingungen des angestellten Verkaufspersonals. Es kann daher im Rahmen einer abstrakten Normenkontrolle ihre Aufhebung verlangt werden. Demgegenüber ist eine direkte Anfechtung der ihnen zugrunde liegenden, im Jahre 1993 verabschiedeten bzw. 1998 revidierten Gesetzesbestimmung (§ 11 Abs. 3 RLG/BS) ausgeschlossen. Sollte sie sich im Rahmen einer vorfrageweisen Überprüfung ihrerseits als verfassungswidrig erweisen, so könnte sie im vorliegenden Verfahren nicht aufgehoben werden, doch bliebe ihr in Bezug auf die angefochtene Verordnung die Anwendung versagt, d.h. sie könnte als Grundlage derselben nicht herangezogen werden.
Auf die staatsrechtliche Beschwerde ist einzutreten.
2. 2.1 Die Beschwerdeführer rügen eine Verletzung des Grundsatzes der derogatorischen Kraft des Bundesrechts (<ref-law>).
Geltend gemacht wird einerseits ein Verstoss gegen das Bundesgesetz vom 13. März 1964 über die Arbeit in Industrie, Gewerbe und Handel (Arbeitsgesetz, ArG; SR 822.11), welches den Arbeitnehmerschutz umfassend und abschliessend regle, weshalb für zu diesem Zweck erlassene kantonale Ladenschlussvorschriften kein Raum mehr bestehe. Vor diesem Hintergrund sei die vorliegend zur Diskussion stehende Regelung bereits auf Gesetzesstufe unzulässig, könne doch gemäss § 11 Abs. 3 RLG/BS die Verlängerung der Öffnungszeiten der Verkaufslokale nur dann gestattet werden, wenn "die beteiligten Arbeitgeber- und Arbeitnehmerorganisationen" damit einverstanden seien. Auch beziehe sich der anvisierte Arbeitnehmerschutz nicht auf die dem Arbeitsgesetz nicht unterstellten Personen und sei die Regelung nicht polizeilich begründet (Aufrechterhaltung der öffentlichen Ruhe). Indem die Verordnung zudem auf einen bestimmten Gesamtarbeitsvertrag abstelle und dessen Einhaltung voraussetze, werde von den Ladeninhabern verlangt, dass sie ihren Angestellten die entsprechenden Lohn- und Überstundenregelungen gewähren müssten, um die verlängerten Öffnungszeiten in Anspruch nehmen zu können. Damit sei aber offensichtlich, dass die Regelung ausschliesslich den Arbeitnehmerschutz im Auge habe, was in unzulässiger Weise in einen durch Bundesrecht abschliessend geregelten Bereich eingreife.
Andererseits bringen die Beschwerdeführer vor, die beanstandeten Vorschriften seien auch mit der abschliessenden bundesrechtlichen Regelung über die Allgemeinverbindlicherklärung von Gesamtarbeitsverträgen nicht vereinbar.
2.2 Der Grundsatz der derogatorischen Kraft des Bundesrechts (<ref-law>) schliesst in Sachgebieten, welche die Bundesgesetzgebung abschliessend geregelt hat, eine Rechtsetzung durch die Kantone aus. In Sachgebieten, die das Bundesrecht nicht abschliessend ordnet, dürfen die Kantone nur solche Vorschriften erlassen, die nicht gegen den Sinn und Geist des Bundesrechts verstossen und dessen Zweck nicht beeinträchtigen oder vereiteln (<ref-ruling> E. 2.2 S. 86 f.; <ref-ruling> E. 3.1 S. 334, 346 E. 3.1 S. 350, 402 E. 2 S. 404; <ref-ruling> E. 5a S. 54, 295 E. 3b S. 299; <ref-ruling> E. 4a S. 68 mit Hinweisen).
Das Bundesgericht überprüft die Verfassungsmässigkeit eines angefochtenen Erlasses im Rahmen einer abstrakten Normenkontrolle mit freier Kognition, jedoch nicht unter allen denkbaren Titeln, sondern beschränkt auf die von den Beschwerdeführern erhobenen Rügen, wobei es sich mit Rücksicht auf die verfassungsmässige Kompetenzordnung im föderalistischen Bundesstaat allgemein eine gewisse Zurückhaltung auferlegt (vgl. <ref-ruling> E. 2.1 S. 31 f., 82 E. 2.1 S. 86, je mit Hinweisen).
Das Bundesgericht überprüft die Verfassungsmässigkeit eines angefochtenen Erlasses im Rahmen einer abstrakten Normenkontrolle mit freier Kognition, jedoch nicht unter allen denkbaren Titeln, sondern beschränkt auf die von den Beschwerdeführern erhobenen Rügen, wobei es sich mit Rücksicht auf die verfassungsmässige Kompetenzordnung im föderalistischen Bundesstaat allgemein eine gewisse Zurückhaltung auferlegt (vgl. <ref-ruling> E. 2.1 S. 31 f., 82 E. 2.1 S. 86, je mit Hinweisen).
2.3 2.3.1 Kantonale oder kommunale Ladenschlussvorschriften dürfen, wie das Bundesgericht in konstanter Rechtsprechung erkannt hat, seit Inkrafttreten des eidgenössischen Arbeitsgesetzes nur noch dem Schutz der Nacht- und Feiertagsruhe (vgl. <ref-law>) bzw. - aus sozialpolitischen Überlegungen - allenfalls jenem der nicht dem Arbeitsgesetz unterstellten Personen (Geschäftsinhaber und ihre Familienangehörigen, gewisse leitende Angestellte) dienen, nicht aber dem Schutz des Verkaufspersonals, welcher durch das Arbeitsgesetz abschliessend geregelt ist (<ref-ruling> E. 2c S. 93; <ref-ruling> E. 2b/bb S. 379; <ref-ruling> E. 7a S. 486; <ref-ruling> E. 3 S. 400 f.; <ref-ruling> E. 3b/3c S. 503 f. sowie E. 5b S. 507; Urteile 2P.184/1998 vom 16. November 1999, E. 1b/aa nicht publ. in <ref-ruling>; Urteile 2P.270/1996 vom 21. März 1997, publ. in: Pra 86/1997 Nr. 101 S. 545 ff., E. 2c; P.1155/1986 vom 3. April 1987, publ. in: ZBl 88/1987 S. 451 ff., E. 6a; 2P.31/1992 vom 29. Juni 1992, E. 2a, sowie 2P.50/2003 vom 7. August 2003, E. 2.2).
2.3.2 Indem nach dem Wortlaut von § 7 Abs. 1 RLV/BS die gestützt auf § 11 Abs. 3 RLG/BS generell verlängerten Öffnungszeiten nur bei "Beachtung" des Gesamtarbeitsvertrages vom 1. Mai 2002 in Anspruch genommen werden dürfen, wird diese Regelung als Druckmittel für Anliegen des Arbeitnehmerschutzes eingesetzt. Der erwähnte Gesamtarbeitsvertrag bezweckt - was an sich zulässig ist - einen gegenüber dem eidgenössischen Arbeitsgesetz erweiterten Arbeitnehmerschutz (so sieht er u.a. eine Zeitgutschrift von 25 % für die Arbeit ab 1830 Uhr vor [Art. 26 GAV], wogegen das Arbeitsgesetz Zeitgutschriften grundsätzlich nur für Nachtarbeit [d.h. von 23-0600 Uhr] und zudem lediglich im Umfang von 10 % vorschreibt [Art. 17b in Verbindung mit <ref-law>]). Die streitige Öffnungszeitenregelung statuiert mittelbar eine Pflicht zur Einhaltung dieser erweiterten Schutzbestimmungen des Gesamtarbeitsvertrages. Dasselbe gilt für § 7a lit. d RLV/BS, wonach die Möglichkeit verlängerter Öffnungszeiten infolge ausserordentlicher örtlicher Verhältnisse (Berücksichtigung der direkten Konkurrenz ausserkantonaler Betriebe mit längeren Öffnungszeiten) auf Verkaufsbetriebe beschränkt wird, welche ihrem Personal mindestens "die gleichen Bedingungen" wie der erwähnte Gesamtarbeitsvertrag gewähren. Beide Verordnungsbestimmungen verfolgen offensichtlich in erster Linie Ziele des Arbeitnehmerschutzes und sind damit mit der Ordnung des eidgenössischen Arbeitsgesetzes, welches diesen Bereich abschliessend regelt, unvereinbar; sie verstossen gegen den Grundsatz der derogatorischen Kraft des Bundesrechts. Davon scheint im Ergebnis auch der Kanton auszugehen, wenn er laut seiner Vernehmlassung die Bestimmung von § 7 Abs. 1 RLV/BS bereits bisher als "rechtlich problematisch" und gegenüber den Verkaufsgeschäften nicht durchsetzbar einstufte bzw. - hinsichtlich § 7a lit. d RLV/BS - auf die Androhung von Sanktionen im Falle von Verstössen gegen die Vereinbarung verzichtet hatte. Dass die angefochtenen Vorschriften hauptsächlich zum Schutz der öffentlichen Ruhe und Ordnung oder jenem der dem eidgenössischen Arbeitsgesetz nicht unterstellten Personen erlassen worden sind, wird vom Kanton jedenfalls mit Grund nicht behauptet. Demzufolge sind § 7 Abs. 1 sowie § 7a lit. d RLV/BS aufzuheben.
Die unstatthafte Verknüpfung der Öffnungszeitenregelung mit Anliegen des Arbeitnehmerschutzes ist, wie die Beschwerdeführer zu Recht hervorheben, im Kern bereits im Gesetz verankert, indem dieses in § 11 Abs. 3 die Zulässigkeit genereller Verlängerungen der Öffnungszeiten durch den Verordnungsgeber von der Zustimmung der "beteiligten Arbeitgeber- und Arbeitnehmerorganisationen" abhängig macht. Der Argumentation des Kantons, wonach es sich bei der genannten Bedingung um eine dem sozialen Frieden dienende, d.h. sozialpolitisch motivierte und damit zulässige Regelung handle, kann nicht gefolgt werden. Wohl dürfen Eingriffe in die Wirtschaftsfreiheit (<ref-law>) nach der bundesgerichtlichen Rechtsprechung auch sozialpolitischen Zielen dienen (vgl. noch zu Art. 31 aBV: BGE <ref-ruling> E. 4 und 5 S. 504 ff.; <ref-ruling> E. 4a S. 422; <ref-ruling> E. 2a S. 15; <ref-ruling> E. 1b S. 131 f. mit weiteren Hinweisen; zu <ref-law>: Urteil 2P.52/2001 vom 24. Oktober 2001, publ. in: ZBl 103/2002 S. 322 ff., E. 4b; vgl. auch <ref-ruling> E. 6.2 S. 50; Botschaft zur neuen Bundesverfassung, in: BBl 1997 I 175; Ulrich Häfelin/Walter Haller, Schweizerisches Bundesstaatsrecht, 5. Aufl., Zürich 2001, N. 663, 670 sowie 672; René Rhinow, Grundzüge des schweizerischen Verfassungsrechts, Basel 2003, S. 513, Rz. 2916 f.; Klaus A. Vallender, in: Ehrenzeller/Mastronardi/Schweizer/Vallender [Hrsg.], Die schweizerische Bundesverfassung, St. Galler Kommentar, Zürich/Lachen SZ 2002, Rz. 34 zu <ref-law>). Diese Möglichkeit besteht aber nur, soweit die einschlägigen Sachnormen des Bundesrechts hiefür Raum lassen, was vorliegend nach dem Gesagten nicht der Fall ist. Das im Gesetz statuierte Erfordernis, wonach eine Verlängerung der ordentlichen Ladenöffnungszeiten u.a. die Zustimmung der beteiligten Arbeitnehmerorganisationen voraussetzt, verknüpft die Regelung des Ladenschlusses in unzulässiger Weise mit Anliegen des Arbeitnehmerschutzes. Ob es überhaupt in der Befugnis des kantonalen Gesetzgebers steht und mit den Grundsätzen demokratischer Gesetzgebung vereinbar ist, die Festlegung der Ladenöffnungszeiten, d.h. das Ausmass hoheitlicher Eingriffe in die Freiheit des Bürgers, von der Zustimmung privater Organisationen abhängig zu machen, braucht hier nicht untersucht zu werden. Die betreffende Klausel in § 11 Abs. 3 RLG/BS vermag schon im Hinblick auf die abschliessende Sachregelung des eidgenössischen Arbeitsgesetzes keine Rechtswirkung zu entfalten, weshalb sie als Grundlage der angefochtenen Verordnungsbestimmungen nicht mehr herangezogen werden kann (oben E. 1.4).
2.4 Die angefochtenen Verordnungsbestimmungen bewirken, wie die Beschwerdeführer im Weiteren mit Recht vorbringen, einen Zwang zum Abschluss bzw. zur Befolgung eines bestimmten Gesamtarbeitsvertrages ohne Einhaltung der für die Allgemeinverbindlicherklärung von Gesamtarbeitsverträgen geltenden bundesrechtlich vorgegebenen formellen und materiellen Voraussetzungen (vgl. <ref-law> sowie Art. 2 f. und 7 ff. des Bundesgesetzes vom 28. September 1956 über die Allgemeinverbindlicherklärung von Gesamtarbeitsverträgen [AVEG; SR 221.215.311]; <ref-ruling> E. 5a S. 19). Es ist davon auszugehen, dass die fragliche Regelung auch unter diesem Aspekt gegen den Grundsatz der derogatorischen Kraft des Bundesrechts verstossen würde (vgl. <ref-ruling> E. 2e S. 111 f.). Die Frage braucht indessen nach dem Gesagten nicht vertieft geprüft zu werden. Im Übrigen kann auch offen bleiben, wieweit die angefochtenen Bestimmungen den allgemeinen Anforderungen an Eingriffe in die Wirtschaftsfreiheit (Art. 27 in Verbindung mit <ref-law>) zu genügen vermögen, nachdem sie schon aus einem anderen Grund aufzuheben sind.
2.5 Zusammenfassend ergibt sich somit, dass § 7 Abs. 1 sowie § 7a lit. d RLV/BS gegen den Grundsatz der derogatorischen Kraft des Bundesrechts (<ref-law>) verstossen und demzufolge in Gutheissung der staatsrechtlichen Beschwerde aufzuheben sind.
Die Beschwerdeführer beantragen zwar lediglich die Aufhebung der "Änderung von § 7 Abs. 1 und § 7a lit. d" RLV/BS. Bei § 7 Abs. 1 RLV/BS ist indessen die als verfassungswidrig erkannte Bedingung im Ingress zentrale Voraussetzung für die Gewährung der in lit. a und b desselben Absatzes festgelegten verlängerten Öffnungszeiten, weshalb es sich rechtfertigt, § 7 Abs. 1 insgesamt, d.h. unter Einschluss von lit. a und b aufzuheben. Demgegenüber genügt es bei § 7a RLV/BS, lediglich lit. d aufzuheben, wird doch die Öffnungszeitenregelung bei ausserordentlichen örtlichen Verhältnissen durch die Streichung dieser einzelnen Bewilligungsvoraussetzung ihres Sinnes nicht entleert, solange die (im neu geschaffenen Verfahren gemäss § 7b RLV/BS zu überprüfenden) zusätzlichen Sachvoraussetzungen von § 7a lit. a bis c RLV/BS in Kraft bleiben.
Welche rechtlichen Konsequenzen die Aufhebung von § 7 Abs. 1 RLV/BS in Bezug auf die generellen Öffnungszeiten zur Folge hat, ob damit alle Ladenbetriebe wieder der Grundordnung gemäss § 6 RLG/BS unterworfen sind, wie der Regierungsrat annimmt, oder ob es, wie die Beschwerdeführer geltend machen, mangels eines zulässigen polizeilichen Interesses an einer Verkürzung der jetzigen Öffnungszeiten bei der gegenwärtigen faktischen Ordnung bleiben muss, ist im vorliegenden Verfahren nicht zu beurteilen. Es ist nötigenfalls Sache des Verordnungsgebers, neue, die Vorgaben des Bundesrechts respektierende Vorschriften zu erlassen.
3. Bei diesem Ausgang des bundesgerichtlichen Verfahrens sind, da der Kanton Basel-Stadt vorliegend nicht in Vermögensinteressen betroffen ist, keine Gerichtskosten zu erheben (Art. 156 Abs. 1 und 2 OG). Der Kanton Basel-Stadt hat die Beschwerdeführer indessen angemessen zu entschädigen (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird gutgeheissen und § 7 Abs. 1 sowie § 7a lit. d RLV/BS werden aufgehoben.
2. Es werden keine Kosten erhoben.
3. Der Kanton Basel-Stadt hat die Beschwerdeführer für das bundesgerichtliche Verfahren mit insgesamt Fr. 8'000.-- zu entschädigen.
4. Dieses Urteil wird den Beschwerdeführern und dem Regierungsrat des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 13. Juli 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: