Sachverhalt:
A. Im Kantonsblatt vom 23. Juli 2003 schrieb das Baudepartement des Kantons Basel-Stadt den Auftrag "Universelle Kommunikationsverkabelung/230-V-Installationen" für das Bernoullianum im offenen Verfahren aus. Als generelle Teilnahmebedingung war u.a. die "Einhaltung der Arbeitsbedingungen gemäss § 5 sowie Nachweis und Kontrolle gemäss § 6 des Gesetzes über öffentl. Beschaffungen des Kantons Basel-Stadt" vorgeschrieben.
Unter den insgesamt neun eingegangenen Angeboten erwies sich dasjenige der X._ AG, B._, mit Fr. 189'916.90 als das günstigste. Die Unternehmung hatte ihrer Offerte eine Bestätigung des Verbandes der Schweizer Maschinen-, Elektro- und Metallindustrie (Swissmem) mit folgendem Wortlaut beigelegt:
"Hiermit bestätigen wir, dass die Firma X._ AG in B._ Mitglied des ASM Arbeitgeberverband der Schweizer Maschinenindustrie ist und damit der Vereinbarung in der Maschinenindustrie vom 1. Juli 1998 untersteht. Im Weiteren bestätigen wir, dass die Firma X._ AG in B._ diesen Vertrag einhält".
B. Mit Fax vom 3. September 2003 teilte das Submissionsbüro des Baudepartements der X._ AG mit, die Durchsicht der Angebotsunterlagen habe ergeben, "dass der erforderliche Nachweis der Einhaltung von § 5 f." des Beschaffungsgesetzes fehle. Massgebend sei gemäss Auskunft des Ständigen staatlichen Einigungsamtes der Gesamtarbeitsvertrag der Schweizerischen Elektro- und Telekommunikations-Installationsbranche (im Folgenden: SETI-GAV). Die X._ AG werde gebeten, "diesen Nachweis" bis spätestens Freitag, 5. September 2003, 16.00 Uhr, an das Baudepartement nachzuliefern.
Mit Schreiben vom 8. September 2003 bestätigte die Gewerkschaft Industrie, Gewerbe, Dienstleistungen (SMUV) dem Baudepartement, dass sieben namentlich genannte Mitarbeiter der X._ AG den Mindestlohn gemäss SETI-GAV erhielten und dass die Gewerkschaft keine Klagen gegen die X._ AG führe.
C. Mit Verfügung vom 15. September 2003 teilte das Baudepartement der X._ AG mit, ihr Angebot sei vom Verfahren ausgeschlossen worden, weil der verlangte Nachweis bezüglich der Einhaltung der Arbeitsbedingungen nicht beigebracht worden sei. Der Zuschlag ging mit Verfügung vom 20. September 2003 zum Preis von Fr. 213'512.15 an die Elektrizitäts Aktiengesellschaft Basel (EAGB).
Auf Rekurs der X._ AG hin bestätigte das Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) mit Urteil vom 16. Dezember 2003 sowohl die Ausschlussverfügung wie auch den Zuschlagsentscheid.
D. Mit Eingabe vom 18. Januar 2004 führt die X._ AG staatsrechtliche Beschwerde beim Bundesgericht mit den Anträgen, das Urteil des Appellationsgerichts Basel-Stadt (als Verwaltungsgericht) vom 16. Dezember 2003 aufzuheben und das Beschaffungsgeschäft direkt der Beschwerdeführerin zuzuschlagen. Eventuell sei die Sache zur Neubeurteilung im Sinne der Erwägungen an das Appellationsgericht zurückzuweisen, subeventuell die Rechtswidrigkeit des angefochtenen Entscheides festzustellen.
Das Baudepartement des Kantons Basel-Stadt beantragt, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Appellationsgericht des Kantons Basel-Stadt schliesst auf Abweisung der Beschwerde. Die Elektrizitäts Aktiengesellschaft Basel (EAGB) hat auf eine Vernehmlassung verzichtet.
E. Am 3. Februar 2004 wies der Abteilungspräsident das gleichzeitig mit der Beschwerdeeinreichung gestellte Gesuch um aufschiebende Wirkung ab.
F. Eine Nachfrage des Instruktionsrichters hat ergeben, dass der Vertrag zwischen dem Baudepartement des Kantons Basel-Stadt und der Elektrizitäts AG Basel über die vorliegend in Frage stehenden Arbeiten am 9./12. Januar 2004 abgeschlossen worden ist.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid, der sich auf kantonales Submissionsrecht stützt und gegen den mangels Zulässigkeit eines anderen eidgenössischen Rechtsmittels nur die staatsrechtliche Beschwerde offen steht (Art. 84 Abs. 2, Art. 86 und Art. 87 OG).
1.2 Die Beschwerdeführerin war am vorliegenden kantonalen Submissionsverfahren beteiligt und ist als ausgeschlossene Bewerberin zur staatsrechtlichen Beschwerde legitimiert (Art. 88 OG). Sie kann, wovon das Appellationsgericht zu Recht ausgegangen ist, nicht nur die Ausschlussverfügung anfechten, sondern darüber hinaus grundsätzlich auch die Aufhebung der im betreffenden Verfahren anschliessend ergangenen Zuschlagsverfügung beantragen. Ist der Zuschlagsentscheid schon in Vollzug gesetzt und mit dem ausgewählten Konkurrenten - wie vorliegend geschehen (vorne "F.-") - bereits ein Vertrag abgeschlossen worden, kann hingegen nur noch die Feststellung der Rechtswidrigkeit der "angefochtenen Verfügung" verlangt werden (vgl. Art. 9 Abs. 3 des Bundesgesetzes vom 6. Oktober 1995 über den Binnenmarkt [Binnenmarktgesetz, BGBM; SR 943.02], <ref-ruling> E. 5b S. 97 f.). Dieser Feststellungsanspruch kann sich richtigerweise nur auf die bereits vollzogenen Sachanordnungen der Submissionsbehörde beziehen, nicht aber auf den diese bestätigenden kantonalen Rechtsmittelentscheid, der bei Begründetheit der staatsrechtlichen Beschwerde schon deshalb aufgehoben werden muss, um eine Korrektur des Kostenspruchs zu ermöglichen. Im Falle einer Gutheissung der staatsrechtlichen Beschwerde stellt das Bundesgericht daher zusätzlich zur Aufhebung des Rechtsmittelentscheides auch die Rechtswidrigkeit des Zuschlagsentscheides fest, sofern diese Frage spruchreif ist. Erscheint die Frage der Rechtswidrigkeit des (vollzogenen) Zuschlags nicht liquid, beschränkt sich das Bundesgericht auf die Aufhebung des kantonalen Rechtsmittelentscheides, und es ist alsdann Sache der kantonalen Rechtsmittelinstanz, aufgrund neuer Beurteilung die allfällige Rechtswidrigkeit des Zuschlags selber festzustellen. Der Subeventualantrag der Beschwerdeführerin (Feststellung der Rechtswidrigkeit des "angefochtenen Entscheides") ist in diesem Sinne zu interpretieren, d.h. es ist gegebenenfalls die Bundesrechtswidrigkeit der streitigen Ausschlussverfügung und des darauf gründenden Zuschlagsentscheides festzustellen, während der diese Anordnungen zu Unrecht schützende kantonale Rechtsmittelentscheid aufzuheben wäre.
Der Antrag auf einen "Direktzuschlag" durch das Bundesgericht ist schon durch den inzwischen erfolgten Vertragsabschluss hinfällig geworden; er wäre zudem mit der kassatorischen Natur der staatsrechtlichen Beschwerde (vgl. <ref-ruling> E. 1.5 mit Hinweisen) nicht vereinbar.
1.3 Nach Art. 90 Abs. 1 lit. b OG muss die Beschwerdeschrift die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft im Verfahren der staatsrechtlichen Beschwerde nur klar und detailliert erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 2 S. 3 f.). Auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein (<ref-ruling> E. b). Macht der Beschwerdeführer - wie hier - eine Verletzung des Willkürverbots geltend, muss er anhand der angefochtenen Subsumtion im Einzelnen darlegen, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet.
2. 2.1 Gemäss § 5 Abs. 1 des basel-städtischen Gesetzes vom 20. Mai 1999 über öffentliche Beschaffungen (Beschaffungsgesetz, BeG) darf ein Auftrag "in der Regel" nur an einen Anbieter erteilt werden, der als Arbeitgeber an einem Gesamtarbeitsvertrag beteiligt ist. Dieser Gesamtarbeitsvertrag muss "die angebotene Arbeitsleistung zum Gegenstand haben" oder branchenverwandt und für die Arbeitnehmer "mindestens gleichwertig" sein. Die Anbieter müssen für die in der Schweiz erbrachten Leistungen die dauernde und vollumfängliche Einhaltung der Gesamtarbeitsverträge nachweisen (§ 5 Abs. 2 lit. a BeG). Massgebend sind die am Sitz der Anbietenden geltenden Gesamtarbeitsverträge. Fehlen dort Gesamtarbeitsverträge, so müssen die am Ort des Sitzes geltenden branchenüblichen Arbeitsbedingungen dauernd und vollumfänglich eingehalten werden (§ 5 Abs. 3 BeG). Der Anbieter muss die Einhaltung dieser Bedingungen auf eigene Kosten gegenüber dem Auftraggeber durch die vom Kanton bezeichneten Stellen erbringen (§ 6 Abs. 1 BeG). Wer die Einhaltung der Arbeitsbedingungen nicht gewährleistet, wird vom Verfahren "in der Regel" ausgeschlossen (§ 8 lit. a BeG). Verlangt wird die Einreichung eines Dokumentes, worin bestätigt wird, dass die Anbieter die Gesamtarbeitsverträge einhalten (§ 2 der Verordnung vom 11. April 2000 zum Gesetz über öffentliche Beschaffungen, BeV). Das Einigungsamt prüft von Amtes wegen oder auf Antrag hin, ob der Anbieter die für öffentliche Beschaffungen verlangten Arbeitsbedingungen einhält (§ 5 Abs. 1 BeV).
2.2 Das Binnenmarktgesetz, auf welches sich die Beschwerdeführerin vorliegend am Rande ebenfalls beruft (S. 8 der Beschwerdeschrift), schliesst derartige Regelungen zur Vermeidung von Wettbewerbsverzerrungen im öffentlichen Beschaffungswesen nicht aus (vgl. Botschaft zum BGBM, BBl 1995 1286; Evelyne Clerc, Commentaire romand, Droit de la concurrence, N. 124 ff. zu Art. 5 BGBM; vgl. auch Peter Galli/Daniel Lehmann/Peter Rechsteiner, Das öffentliche Beschaffungswesen in der Schweiz, Zürich 1996, N. 245).
Es mag zwar fraglich sein, wieweit es statthaft ist, für die Zulassung als Anbieter den formellen Beitritt zu einem Gesamtarbeitsvertrag zu verlangen, ohne dass das hiefür vorgesehene Verfahren sowie die gesetzlichen Voraussetzungen für einen derartigen (indirekten) Zwang eingehalten werden (Clerc, a.a.O., N. 130, mit Hinweis auf <ref-ruling> E. 2 f. S. 112). Nach § 5 des basel-städtischen Beschaffungsgesetzes wird jedoch von den Anbietern die Beteiligung an einem Gesamtarbeitsvertrag nur "in der Regel" verlangt, was gemäss Feststellung des Appellationsgerichts die Möglichkeit beinhaltet, die Einhaltung der orts- und branchenüblichen Arbeitsbedingungen bei Unternehmen, die keinem Gesamtarbeitsvertrag unterstellt sind, anderswie nachzuweisen. Mangels einer hinreichend begründeten Rüge (Art. 90 OG, E. 1.3) - der blosse Hinweis auf frühere Vorbringen im kantonalen Verfahren (vgl. S. 8 unten der Beschwerdeschrift) genügt nicht (<ref-ruling> E. 4a S. 30 mit Hinweis) - ist auf diese letztere Problematik vorliegend nicht einzugehen.
3. Die Beschwerdeführerin hat sich der Regel von § 5 Abs. 1 des basel-städtischen Beschaffungsgesetzes unterzogen und zusammen mit ihrem Angebot die Bestätigung des Verbandes der Schweizer Maschinen-, Elektro- und Metallindustrie eingereicht, wonach sie Mitglied dieses Verbandes und damit dem betreffenden Gesamtarbeitsvertrag (im Folgenden: Swissmem-GAV) unterworfen ist. Das Baudepartement leitete diese Erklärung zur Prüfung an das Ständige staatliche Einigungsamt weiter, welches am 4. September 2003 dem Departement mitteilte, für die zu vergebenden Elektro-Installationen sei der Gesamtarbeitsvertrag der Schweizerischen Elektro- und Telekommunikations-Installationsbranche (im Folgenden: SETI-GAV) massgebend; die Vereinbarung in der Maschinenindustrie enthalte, im Gegensatz zum genannten SETI-GAV, keine festgelegten Minimallöhne und sei somit nicht gleichwertig. Das Baudepartement wies daraufhin die Beschwerdeführerin auf das Fehlen des Nachweises der Einhaltung von "§ 5 f. Beschaffungsgesetz" hin; massgebend sei der Gesamtarbeitsvertrag der Schweizerischen Elektro- und Telekommunikations-Installationsbranche. "Dieser Nachweis" sei bis spätestens 5. September 2003, 16.00 Uhr, nachzuliefern. Da die von der Beschwerdeführerin in der Folge - nach Ablauf dieser Frist - noch eingereichten weiteren Unterlagen als ungenügend erachtet wurden, wurde sie (als günstigste Anbieterin neben acht in Basel ansässigen, offenbar je dem SETI-GAV unterworfenen Mitbewerbern) vom Verfahren ausgeschlossen.
4. 4.1 Streitig ist zunächst, ob die kantonalen Instanzen annehmen durften, der Swissmem-GAV habe nicht, wie in § 5 des Beschaffungsgesetzes verlangt, die "angebotene Arbeitsleistung zum Gegenstand". Das Baudepartement hatte dies, gestützt auf eine entsprechende Stellungnahme des Ständigen staatlichen Einigungsamtes, verneint und wurde in diesem Punkt vom Appellationsgericht geschützt. Zur Begründung führt das Gericht im angefochtenen Urteil aus, der Swissmem-GAV sei weniger auf die Installationsbranche als vielmehr auf die "Metall- und Elektromaschinenindustrie" zugeschnitten, weshalb zulässigerweise der Gesamtarbeitsvertrag der Schweizerischen Elektro- und Telekommunikations-Installationsbranche (SETI-GAV) habe als massgebend erachtet werden dürfen, zumal dieser GAV mit Ausnahme des Kantons Genf für alle Arbeitnehmer dieser Branche in der Schweiz Geltung habe. Der Swissmem-GAV, dem die Beschwerdeführerin angehöre, könne im Sinne von § 5 Abs. 1 des Beschaffungsgesetzes nur als "branchenverwandt" gelten, womit der Anbieter die Gleichwertigkeit mit dem SETI-GAV nachweisen und diesen Nachweis dem Angebot beilegen müsse.
4.2 Diese Betrachtungsweise beruht, entgegen den Vorbringen der Beschwerdeführerin, nicht auf einer unhaltbaren, geradezu willkürlichen Anwendung von § 5 Abs. 1 des Beschaffungsgesetzes. Zwar ist das Appellationsgericht ungenauerweise davon ausgegangen, der Swissmem-GAV sei auf die Metall- und "Elektromaschinenindustrie" zugeschnitten (S. 6 des angefochtenen Urteils), während nach Darstellung der Beschwerdeführerin dieser GAV den Bereich der Elektroindustrie insgesamt erfasst (wozu auch die Installation von Verkabelungen für PC-Applikationen gehören soll). Doch ergibt sich schon aus der gewählten Bezeichnung, dass der Swissmem-GAV auf Betriebe aus dem Bereich der Industrie (Produktion von Gütern) ausgerichtet ist, während die Installation von Leitungen naturgemäss eher Betrieben gewerblichen Charakters vorbehalten ist. Es erscheint insoweit vertretbar, den spezielleren, praktisch in der ganzen Schweiz befolgten GAV für die Elektro- und Telekommunikationsbranche als massgebenden Vertrag im Sinne von § 5 Abs. 1 BeG zu betrachten.
4.3 Der gegenteilige Standpunkt der Beschwerdeführerin, wonach im gleichen Submissionsverfahren für verschiedene Anbieter verschiedene Gesamtarbeitsverträge zur Anwendung kommen könnten, kann sich auf den Wortlaut von § 5 Abs. 3 des Beschaffungsgesetzes stützen und ist ebenfalls vertretbar. Wie der vorliegende Fall zeigt, kann es sodann durchaus vorkommen, dass die Tätigkeitsbereiche von Unternehmen, die verschiedenen Gesamtarbeitsverträgen angeschlossen sind, sich teilweise überschneiden oder dass ein nur einem Gesamtarbeitsvertrag angeschlossenes Unternehmen Tätigkeiten ausübt, für die ein anderer Gesamtarbeitsvertrag ebenfalls möglich oder sogar sachbezogener wäre.
Im vorliegenden Fall wurde in der Ausschreibung der massgebende Gesamtarbeitsvertrag nicht bereits bestimmt, sondern bloss in allgemeiner Weise auf die gesetzlichen Vorschriften hingewiesen (vgl. Ziff. 3.1 lit. a der Generellen Teilnahmebedingungen). Die Erklärung des Ständigen staatlichen Einigungsamtes, wonach der SETI-GAV massgebend sei, wurde erst nach Einreichung der Angebote bekannt. Es darf der Beschwerdeführerin unter diesen Umständen nicht zum Nachteil gereichen, wenn sie den für ihren Betrieb geltenden Gesamtarbeitsvertrag (den Swissmem-GAV) als massgebend betrachtete und ihrem Angebot eine entsprechende Erklärung beilegte. Der in der Vernehmlassung des Kantons (S. 11) gezogene Vergleich mit einem Bauunternehmer, welcher sich dem Hutmacher-Gesamtarbeitsvertrag anschliesse, um nur diesem GAV entsprechende Löhne zu bezahlen, ist abwegig. Es wird von keiner Seite in Abrede gestellt, dass die vorliegend auszuführenden Arbeiten auch dem Bereich der Elektroindustrie zugerechnet werden können, für welche der Swissmem-GAV gilt, auch wenn daneben noch ein speziellerer Gesamtarbeitsvertrag für die Elektroinstallationsbranche besteht, dessen Bedingungen nach Auffassung der kantonalen Behörden für die streitige Vergebung allein massgebend sein sollen. Wenn die Submissionsbehörde nicht auf den Swissmem-GAV, sondern auf diesen letzteren Gesamtarbeitsvertrag (SETI-GAV) abstellen wollte, hatte sie der Beschwerdeführerin ordnungsgemäss Gelegenheit zu geben, die Gleichwertigkeit ihres GAV mit dem als massgebend erachteten anderen GAV darzutun.
4.4 Das vom 3. September 2003 datierte, aber auch nach Auffassung des Appellationsgerichtes offenbar erst am 4. September 2003 per Fax versandte Schreiben des Baudepartementes setzte der Beschwerdeführerin hiefür nicht nur eine extrem kurze Frist bis zum 5. September 2003 (16.00 Uhr), sondern es war zudem auf eine Weise abgefasst, welche die Beschwerdeführerin im Unklaren darüber liess, was unter dem verlangten zusätzlichen "Nachweis" zu verstehen war. Von der in § 5 Abs. 1 des Beschaffungsgesetzes umschriebenen Rechtslage her konnte an sich nur noch der Nachweis der Gleichwertigkeit des branchenverwandten Swissmem-GAV in Frage kommen. Dass dieser letztere GAV vom Submissionsbüro wenigstens als "branchenverwandt" anerkannt wurde, ging aus dem Schreiben des Baudepartementes indessen nicht hervor, weshalb die Interpretation der Beschwerdeführerin, es sei von ihr der Nachweis des (kurzfristigen) Anschlusses an den SETI-GAV verlangt worden, nicht zum vornherein abwegig war. Für diese Auslegung lässt sich anführen, dass dem Baudepartement bei Abfassung seines Schreibens vom 3. September 2003 bereits eine (im Schreiben nicht mitübernommene) - handschriftliche - Erklärung des Ständigen staatlichen Einigungsamtes vorlag, wonach der Swissmem-GAV mangels festgelegter Minimallöhne mit dem SETI-GAV nicht gleichwertig sei. Insofern bestand nach der damals bereits vorliegenden, aber nach aussen nicht bekannt gegebenen Beurteilung des Einigungsamtes für den Nachweis der Gleichwertigkeit der beiden Gesamtarbeitsverträge gar kein Raum mehr. So oder anders war die gewährte Frist von einem Tag extrem kurz und jedenfalls nicht ausreichend, um die von der zuständigen Stelle geforderte Bestätigung der Gleichwertigkeit des Gesamtarbeitsvertrages zu erwirken (vgl. § 6 Abs. 1 BeG, §§ 2 und 3 BeV).
Gemäss den Feststellungen im angefochtenen Urteil (S. 8) wurde der Beschwerdeführerin denn auch telefonisch eine Nachfrist bis zum 8. September 2003 gewährt, innerhalb welcher die Gewerkschaft SMUV gegenüber dem Baudepartement bestätigte, dass die Mindestlöhne des SETI-GAV in Bezug auf sieben namentlich genannte, für die Ausführung der streitigen Arbeiten vorgesehene Mitarbeiter der Beschwerdeführerin eingehalten seien. Das Submissionsbüro und auch das Appellationsgericht erachteten diese Erklärung als unzureichend. Erforderlich wäre nach Auffassung der kantonalen Behörden der Nachweis gewesen, dass sämtliche Arbeitnehmer der Beschwerdeführerin oder jedenfalls alle jene, welche für die ausgeschriebenen Arbeiten grundsätzlich in Frage kommen könnten, Arbeitsbedingungen hätten, welche mit denen vom SETI-GAV gewährten gleichwertig seien. Es genüge nicht, wenn ein Anbieter belegen könne, dass er im Rahmen des ausgeschriebenen Auftrages kein Lohndumping betreibe; das kantonale Beschaffungsgesetz (§ 5 Abs. 2 lit. a) verlange, dass die massgebenden Arbeitsbedingungen "dauernd und vollumfänglich" eingehalten würden.
Das Appellationsgericht kam zum Schluss, dieser Nachweis sei von der Beschwerdeführerin innert der ihr vom Submissionsbüro gesetzten Frist nicht erbracht worden, weshalb es den bei ihm erhobenen Rekurs abwies. Die beiden erst im Rekursverfahren eingereichten Belege der Gewerkschaften SMUV und SYNA vom 24. September 2003, welche nach Auffassung des Appellationsgerichts als Nachweis im Sinne von § 6 BeG "wohl ausgereicht" hätten, seien verspätet und daher nicht zu berücksichtigen.
5. Dass die Beschwerdeführerin den Nachweis der Gleichwertigkeit der Gesamtarbeitsverträge nicht rechtzeitig erbracht hat, ist nach dem Gesagten in erster Linie auf das der Sachlage nicht gerecht werdende Schreiben des Baudepartementes vom 3. September 2003 zurückzuführen. Wenn die Submissionsbehörde gestützt auf die Erklärung des Einigungsamtes den Swissmem-GAV - obwohl er die ausgeschriebenen Arbeiten ebenfalls durchaus zum Gegenstand haben konnte - nicht als massgebend erachten wollte, hatte sie für den Nachweis der Gleichwertigkeit dieses Gesamtarbeitsvertrages eine angemessene Frist einzuräumen und zugleich zu sagen, auf welche Kriterien sie für diesen Vergleich abstellen wollte (beispielsweise Beschränkung des Vergleichs auf Arbeitszeiten und tarifliche Minimallöhne, Festlegung des in den Vergleich einzubeziehenden Personals oder Betriebsteils), zumal sich weder aus dem Beschaffungsgesetz noch aus der zugehörigen Verordnung hierüber etwas Näheres entnehmen lässt und offenbar auch die von der Beschwerdeführerin beigezogenen Gewerkschaftsvertreter, welche mit der Submissionsbehörde Rücksprache genommen hatten, zunächst nicht wussten, was mit der Formulierung "Wir bitten Sie, diesen Nachweis bis 5. September 2003, 16.00 Uhr (....) nachzuliefern" gemeint war. Auch die Unklarheit der kantonalen Vorschriften über die Zuständigkeit für die Ausstellung der erforderlichen Bestätigungen (§ 6 Abs. 1 BeG, § 3 Abs. 1 BeV) schuf das Bedürfnis nach präzisierenden Anweisungen. Das Submissionsbüro war dazu umso eher gehalten, als es durch den Wortlaut seines Schreibens vom 3. September 2003 und insbesondere durch die dort gewährte extrem kurze Frist zu möglichen Missverständnissen selber entscheidend beigetragen hatte. Dass der Nachweis der Gleichwertigkeit der Gesamtarbeitsverträge gemäss Gesetz von den Anbietern erbracht werden muss, ändert nichts an der Pflicht der Submissionsbehörde, den Gegenstand des geforderten Nachweises - sei es bereits in der Ausschreibung oder aber nachträglich bei auftauchenden Unklarheiten - nötigenfalls zu bestimmen. Aufgrund des geschilderten Ablaufs der Ereignisse drängt sich der Schluss auf, dass das Verhalten der kantonalen Behörden - zwar nicht durch das verwendete Kriterium, aber durch dessen Handhabung im konkreten Fall - darauf ausgerichtet war, die ortsfremde Beschwerdeführerin als deutlich günstigste Anbieterin aus dem Verfahren auszuschliessen. Das Ergebnis des Submissionsverfahrens erscheint insgesamt als stossend und mit dem Willkürverbot (Art. 9 BV) nicht vereinbar.
6. Die staatsrechtliche Beschwerde ist daher gutzuheissen, soweit darauf einzutreten ist, und das angefochtene Urteil aufzuheben. Zudem ist festzustellen (vgl. E. 1.2), dass der Ausschluss der Beschwerdeführerin aus dem Vergabeverfahren und der gestützt hierauf ergangene Zuschlagsentscheid vom 20. September 2003 im Sinne der vorstehenden Erwägungen bundesrechtswidrig sind.
Bei diesem Verfahrensausgang hat der Kanton Basel-Stadt, der vorliegend Vermögensinteressen im Sinne von Art. 156 Abs. 2 OG wahrnimmt, die Kosten des bundesgerichtlichen Verfahrens zu tragen und die Beschwerdeführerin für dieses Verfahren angemessen zu entschädigen (Art. 159 OG, vgl. Urteil 2P.342/1999 vom 31. Mai 2000, publ. in: Pra 89/2000 Nr. 150 S. 896).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird gutgeheissen, soweit darauf einzutreten ist, und der Entscheid des Appellationsgerichts des Kantons Basel-Stadt (als Verwaltungsgericht) vom 16. Dezember 2003 aufgehoben.
2. Es wird festgestellt, dass der am 15. September 2003 verfügte Ausschluss der Beschwerdeführerin aus dem Vergabeverfahren und der gestützt hierauf ergangene Zuschlagsentscheid vom 20. September 2003 im Sinne der Erwägungen bundesrechtswidrig sind.
3. Die Gerichtsgebühr von Fr. 5'000.-- wird dem Kanton Basel-Stadt auferlegt.
4. Der Kanton Basel-Stadt hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 5'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien, dem Baudepartement und dem Appellationsgericht (als Verwaltungsgericht) des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 13. Juli 2004
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: