Sachverhalt:
A. Die Stadt Adliswil schrieb am 20. August 2004 im selektiven Verfahren die öffentliche Vergabe der Kehrichtabfuhr sowie weiterer Dienstleistungen des Abfallwesens für die Jahre 2006-2012 aus. Von den acht Unternehmen, welche sich um Offertstellung bewarben, liess die Stadt Adliswil fünf zum Einreichen eines Angebots zu (Beschluss vom 7. Oktober 2004). Am 19. April 2005 schloss der Stadtrat die S._ AG, welche mit einem Preis von 647'684.80 Franken pro Jahr das billigste Angebot eingereicht hatte, vom Verfahren aus; gleichzeitig erteilte er der einheimischen B._ AG den Zuschlag (Preis von 824'662.65 Franken). Die drei übrigen Unternehmen hatten Preise von 769'425.70, 833'995.05 bzw. 938'489.75 Franken offeriert.
B. Die S._ AG, beschwerte sich erfolgreich beim Verwaltungsgericht des Kantons Zürich, welches den Stadtratsbeschluss sowohl betreffend ihren Ausschluss als auch hinsichtlich des Zuschlags an die B._ AG aufhob und die Sache "zu neuem Entscheid über den Zuschlag im Sinn der Erwägungen" an den Stadtrat zurückwies (Entscheid vom 25. Januar 2006).
C. Am 6. März 2006 hat die B._ AG beim Bundesgericht staatsrechtliche Beschwerde eingereicht und die Aufhebung des Verwaltungsgerichtsentscheids verlangt (Verfahren 2P.70/2006). Die S._ AG, und das Verwaltungsgericht des Kantons Zürich schliessen je auf Abweisung der Beschwerde, soweit darauf einzutreten sei.
Am 6. März 2006 hat auch die Stadt Adliswil staatsrechtliche Beschwerde beim Bundesgericht eingereicht und ebenfalls die Aufhebung des Verwaltungsgerichtsentscheids verlangt (Verfahren 2P.71/2006). Die B._ AG beantragt die Gutheissung dieser zweiten Beschwerde, während die S._ AG, und das Verwaltungsgericht des Kantons Zürich - wie im Parallelverfahren - je auf Abweisung der Beschwerde schliessen, soweit darauf einzutreten sei.
D. Am 27. März 2006 hat der Präsident der II. öffentlichrechtlichen Abteilung des Bundesgerichts beiden Beschwerden antragsgemäss aufschiebende Wirkung erteilt.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Auf das vorliegende Verfahren findet noch das bis Ende 2006 geltende Bundesgesetz vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege (OG) Anwendung (vgl. Art. 132 Abs. 1 des am 1. Januar 2007 in Kraft getretenen Bundesgesetzes vom 17. Juni 2005 über das Bundesgericht [BGG; SR 173.110]).
1.2 Die beiden staatsrechtlichen Beschwerden (2P.70/2006 und 2P.71/2006) richten sich gegen das gleiche Urteil und werfen weitgehend die gleichen Rechtsfragen auf; wegen ihres engen Zusammenhangs sind die beiden Verfahren zu vereinigen (Art. 24 BZP in Verbindung mit Art. 40 OG).
2. 2.1 Angefochten ist ein kantonal letztinstanzlicher Entscheid, der sich auf kantonales Recht stützt und gegen den auf Bundesebene deshalb nur die staatsrechtliche Beschwerde offen steht (Art. 86 Abs. 1 in Verbindung mit Art. 84 Abs. 2 OG). Allerdings handelt es sich beim angefochtenen Entscheid um einen Rückweisungsentscheid, welcher - weil er das kantonale Verfahren nicht abschliesst - als Zwischenentscheid im Sinne von Art. 87 Abs. 2 OG gilt (vgl. <ref-ruling> E. 1a S. 253, mit Hinweisen), gegen den die staatsrechtliche Beschwerde grundsätzlich nur dann offen steht, wenn dem Betroffenen ein nicht wiedergutzumachender rechtlicher Nachteil droht.
2.2 Ein nicht wiedergutzumachender Nachteil für die Beschwerdeführerin 1 ist weder geltend gemacht noch ersichtlich. Ein solcher liegt aber für die Stadt Adliswil vor: Nach der bundesgerichtlichen Rechtsprechung ist es der betroffenen Gemeinde nicht zuzumuten, einer von ihr als falsch erachteten Weisung Folge zu leisten, um alsdann ihren eigenen Entscheid anzufechten, wenn sie - wie hier - durch einen Rückweisungsentscheid gezwungen wird, entgegen ihrer Auffassung eine neue Anordnung zu erlassen (<ref-ruling> E. 3.3 S. 318; <ref-ruling> E. 1b S. 7). Mithin ist die Stadt Adliswil, welche durch den angefochtenen Entscheid in ihrer Eigenschaft als Trägerin hoheitlicher Gewalt berührt wird, zur staatsrechtlichen Beschwerde wegen Verletzung ihrer Autonomie befugt. Ob ihr im vorliegenden Zusammenhang tatsächlich Autonomie zusteht, ist nicht eine Frage des Eintretens, sondern bildet Gegenstand der materiell-rechtlichen Beurteilung (<ref-ruling> E. 1.1 S. 412; <ref-ruling> E. 1.2 S. 139).
2.3 Ist auf die form- und fristgerechte Autonomiebeschwerde der Stadt Adliswil einzutreten, so ist auch die staatsrechtliche Beschwerde der Beschwerdeführerin 1 zu behandeln, wiewohl dieser selbst kein nicht wiedergutzumachender Nachteil droht. Der Beschwerdeführerin 1 ist zuzustimmen, dass ein anderes Vorgehen bei der gegebenen Verfahrenslage der Prozessökonomie, welcher die Regelung von Art. 87 OG gerade dienen soll (vgl. <ref-ruling> E. 1b S. 254; vgl. auch <ref-ruling> E. 12 S. 329), widersprechen würde. Die Beschwerdeführerin 1 ist in rechtlich geschützten Interessen betroffen, zumal der angefochtene Verwaltungsgerichtsentscheid den ihr erteilten Zuschlag aufgehoben hat (vgl. Art. 88 OG).
2.4 Die staatsrechtliche Beschwerde muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Entscheid verletzt worden sein sollen (Art. 90 Abs. 1 lit. b OG). Das Bundesgericht untersucht nicht von Amtes wegen, ob ein kantonaler Hoheitsakt verfassungsmässig ist, sondern prüft nur rechtsgenügend vorgebrachte, klar erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 2 S. 3 f.; <ref-ruling> E. 1d S. 201, mit Hinweisen). Wird eine Verletzung des Willkürverbots (Art. 9 BV) geltend gemacht, genügt es nicht, wenn der Beschwerdeführer bloss den angefochtenen Entscheid kritisiert, wie er dies in einem appellatorischen Verfahren tun könnte, bei dem die Rechtsmittelinstanz die Rechtsanwendung frei überprüfen kann. Er muss deutlich dartun, welche Vorschriften oder allgemein anerkannten Rechtsgrundsätze die kantonalen Behörden in einer gegen Art. 9 BV verstossenden Weise verletzt haben sollen (vgl. <ref-ruling> E. 4b S. 12). Soweit die weitschweifigen Beschwerdeschriften diesen Anforderungen nicht genügen und sich in appellatorischer Kritik erschöpfen, ist auf sie nicht einzugehen.
3. 3.1 Art. 50 Abs. 1 BV gewährleistet die Gemeindeautonomie nach Massgabe des kantonalen Rechts, welches den Gemeinden vorliegend ausdrücklich Autonomie einräumt (vgl. Art. 85 der neuen Verfassung des Kantons Zürich vom 27. Februar 2005). Über Autonomie verfügt eine Gemeinde in jenen Sachbereichen, welche der Kanton nicht abschliessend ordnet, sondern ihr - ganz oder teilweise - zur Regelung überlässt, sofern ihr dabei eine relativ erhebliche Entscheidungsfreiheit eingeräumt wird (vgl. BGE <ref-ruling> E. 2a S. 8; <ref-ruling> E. 8b S. 290). Vorliegend geht es um die öffentliche Vergabe der kommunalen Kehrichtversorgung. Dabei ist die Stadt Adliswil zwar an die einschlägigen Submissionsvorschriften gebunden, es stehen ihr jedoch mannigfaltige Entscheidungsbefugnisse zu, namentlich bei der Festlegung des Verfahrens, der Zuschlagskriterien und schliesslich beim Zuschlag selber. Sie verfügt deshalb bei der Vergabe öffentlicher Aufträge über eine relativ erhebliche Entscheidungsfreiheit und damit über Autonomie im dargestellten Sinne (vgl. <ref-ruling> E. 5.2 S. 320; vgl. auch <ref-ruling> E. 2.2 S. 414).
3.2 Das Bundesgericht prüft die Anwendung des kantonalen Submissionsrechts (hier der Zürcher Submissionsverordnung vom 23. Juli 2003 [SubmV/ZH]) durch die kantonale Rechtsmittelinstanz nur unter dem Gesichtswinkel der Willkür; dasselbe gilt für die Interpretation der Ausschreibungsunterlagen und für die Feststellung des Sachverhalts. Demgegenüber steht ihm bei der Beurteilung von Konkordats- und Staatsvertragsbeschwerden (Art. 84 Abs. 1 lit. b u. lit. c OG) grundsätzlich freie Kognition zu (vgl. <ref-ruling> E. 6 S. 98 f., mit Hinweisen).
4. 4.1 Die Stadt Adliswil hatte in ihren Ausschreibungsunterlagen in Aussicht gestellt, dass sie "ungewöhnlich niedrige Angebote" einer besonderen Prüfung hinsichtlich Preisbildung unterziehen und vom Anbieter den Nachweis einer vertragskonformen Erfüllung des Auftrags verlangen werde. Die Offerte der Beschwerdegegnerin war mit einem Preis vom 647'684.80 Franken knapp 16 Prozent billiger als das zweitgünstigste Angebot und rund 21 Prozent billiger als jenes der Beschwerdeführerin 1 (vgl. lit. A), weshalb die Stadt Adliswil von der Beschwerdegegnerin die Offenlegung ihrer Kalkulationsgrundlagen verlangte. Aufgrund dieser kam sie zum Schluss, die Beschwerdegegnerin sei von unrealistischen Annahmen ausgegangen und habe kein kostendeckendes Angebot unterbreitet. Weil sie eine vertragskonforme Erbringung der ausgeschriebenen Dienstleistungen unter den gegebenen Umständen für nicht gewährleistet hielt, schloss sie die Beschwerdegegnerin vom Vergabeverfahren aus.
4.2 Das Verwaltungsgericht kam demgegenüber zum Schluss, es bestehe kein hinreichender Grund, die Beschwerdegegnerin vom Verfahren auszuschliessen. Der tiefe Preis eines Angebots als solcher stelle keinen Ausschlussgrund dar, selbst wenn er tatsächlich nicht kostendeckend sein sollte. Auch Mängel in der Preiskalkulation eines Anbieters könnten einen Ausschluss nur indirekt rechtfertigen: Zum einen dann, wenn sie auf ungenügende Fachkenntnisse schliessen liessen, und zum anderen, wenn sie beim Anbieter zu Verlusten führten und dessen wirtschaftliche Leistungsfähigkeit nicht ausreiche, um diese Einbusse zu verkraften. Nicht zulässig sei aber, allein aus allfälligen Kalkulationsmängeln im streitigen Angebot zu schliessen, die Beschwerdegegnerin vermöge die vertragskonforme Erbringung des Auftrags nicht zu gewährleisten. Andere Anhaltspunkte dafür, dass Zweifel an der Leistungsfähigkeit der Beschwerdegegnerin gerechtfertigt seien, gebe es keine. Insbesondere sei diese seit Jahrzehnten auf dem Gebiet der Entsorgung und des Transportwesens tätig und besorge bereits die Kehrichtabfuhr in fünf Gemeinden. Zudem sei das "Sicherheitsbedürfnis" des Gemeinwesens hinsichtlich der Qualität der Ausführung der Kehrichtabfuhr wesentlich geringer als etwa bei einem anspruchsvollen Bauauftrag, so dass ein vorschneller Ausschluss eines Bewerbers hier umso weniger gerechtfertigt werden könne. Das Risiko beschränke sich für die Stadt Adliswil darauf, während einer gewissen Zeit eine unbefriedigende Leistungserbringung hinnehmen zu müssen.
4.3 Es ist unbestritten, dass die Vergabebehörde bezüglich eines ungewöhnlich billigen Angebots weitere Erkundigungen einholen und dieses gegebenenfalls vom weiteren Vergabeverfahren ausschliessen kann (vgl. § 28 lit. j SubmV/ZH und Art. XIII Ziff. 4 lit. a des internationalen Übereinkommens vom 15. April 1994 über das öffentliche Beschaffungswesen [Government Procurement Agreement, GPA; SR 0.632.231.422], welches neuerdings auch auf kommunale Vergabeverfahren Anwendung findet [Anhang I Annex 2 zum Übereinkommen in der Fassung vom 7. Februar 2003; www.wto.org/english/tratop_e/ gproc_e/che2.doc]; vgl. diesbezüglich Art. 2 des Abkommens vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft und der Europäischen Gemeinschaft über bestimmte Aspekte des öffentlichen Beschaffungswesens [SR 0.172.052.68]). Diese Regelung zielt indessen nicht etwa darauf ab, den Zuschlag für ein gegebenenfalls nicht kostendeckendes Angebot zu verhindern; Sinn und Zweck ist vielmehr, sicherzustellen, dass nur jene Anbieter in die engere Auswahl kommen, welche die nachgefragte Leistung auch tatsächlich erbringen können. Ein ungewöhnlich tiefer Offertpreis ist diesbezüglich relevant, weil er ein Indiz für ein unseriöses Angebot darstellen kann. Durch die zusätzlichen Auskünfte, welche die Vergabebehörde vom betreffenden Bewerber einholt, soll ein solches frühzeitig erkannt werden. Die Regelung von Art. XIII Ziff. 4 lit. a GPA darf indessen nicht dazu führen, dass ein seriöser Anbieter allein deswegen vom Vergabeverfahren ausgeschlossen wird, weil er - aus welchen Gründen auch immer - im konkreten Fall ein besonders günstiges (gegebenenfalls nicht kostendeckendes) Angebot unterbreitet hat. Wie das Verwaltungsgericht richtig ausgeführt hat, ist ein Ausschluss vom Verfahren nur gerechtfertigt, wenn zusätzlich Anlass besteht, an der Fähigkeit des Anbieters zur Erfüllung des ausgeschriebenen Auftrags zu zweifeln.
4.4 Entsprechendes ist gemäss den Feststellungen des Verwaltungsgerichts hier nicht der Fall. Zwar beanstandet die Stadt Adliswil die dahingehende Sachverhaltsfeststellung des Verwaltungsgerichts als willkürlich, vermag aber deren offensichtliche Unhaltbarkeit mit ihren weitgehend appellatorischen Vorbringen (vgl. E. 2.4) nicht darzutun (vgl. <ref-ruling> E. 1b S. 30). Insbesondere legt sie nicht schlüssig dar, weshalb die von der Beschwerdegegnerin im Vergabeverfahren vorgelegten guten Referenzen nicht aussagekräftig sein sollen. Es mag sein, dass sich die örtlichen Verhältnisse und die organisatorischen Anforderungen von Gemeinde zu Gemeinde unterscheiden. Doch ist nicht einzusehen, wieso eine erfahrene Unternehmung, welche die Kehrichtabfuhr für sechs Gemeinden (teils jahrzehntelang) offenbar zu deren Zufriedenheit besorgt hat, die gleiche Leistung für die Stadt Adliswil nicht zu erbringen vermöchte. Dies umso weniger, als zu den bisherigen Auftraggebern mit den Städten Dietikon und Dübendorf zwei Gemeinden gehören, die noch grösser sind als die Stadt Adliswil.
4.5 Nach dem Gesagten ist nicht zu beanstanden, dass das Verwaltungsgericht den Ausschluss der Beschwerdegegnerin aufgehoben hat; was die Stadt Adliswil und die Beschwerdeführerin 1 dagegen vorbringen, geht an der Sache vorbei: Zunächst kann keine Rede davon sein, dass im angefochtenen Entscheid eine unzulässige "Umkehr der Beweislast" vorgenommen wird. Unterzieht die Vergabebehörde ein ungewöhnlich billiges Angebot einer näheren Prüfung, so hat der betreffende Bewerber zusätzliche Informationen zu liefern und seine Berechnungen zu erklären. Gestützt auf diese weiterführenden Auskünfte bildet sich die Behörde ein Urteil über die Seriosität des Angebots. Auch wenn in § 28 lit. j SubmV/ZH vom "Nachweis" gesprochen wird, "dass die Teilnahmebedingungen eingehalten und die Auftragsbedingungen erfüllt werden können", wird insoweit kein Beweis im rechtstechnischen Sinne geführt. Weiter ist im vorliegenden Zusammenhang keine Verletzung des rechtlichen Gehörs ersichtlich. Zwar hat das Verwaltungsgericht festgestellt, dass für eine abschliessende Beurteilung der Berechnungsmethoden der Beschwerdegegnerin an sich eine Expertise erforderlich wäre; es durfte jedoch nach dem Gesagten zulässigerweise auf das Einholen einer solchen verzichten. Fehler in der Kalkulation bzw. ein unter den Selbstkosten liegender Preis vermögen für sich allein den Ausschluss einer Offerte vom weiteren Verfahren nicht zu rechtfertigen. Weil sich die Kritik der Stadt Adliswil an der Offerte der Beschwerdegegnerin gemäss den willkürfreien Feststellungen des Verwaltungsgerichts auf diese Punkte beschränkt hatte, war die Validität der streitigen Kalkulationen zum Vornherein nicht ausschlaggebend und ein Ausschluss des Angebots so oder anders nicht gerechtfertigt. Es braucht deshalb nicht weiter auf die Ausführungen der Stadt Adliswil eingegangen zu werden, mit denen sie zu den weiteren diesbezüglichen Erwägungen des Verwaltungsgerichts (geringeres "Sicherheitsbedürfnis", Möglichkeit einer Vertragsauflösung bei schlechter Erfüllung des Auftrags sowie "Eckwerte" gemäss Ausschreibungsunterlagen) Stellung nimmt. Nicht rechtsgenüglich dargetan wird von der Beschwerdeführerin 1, inwiefern im vorliegenden Zusammenhang die Wirtschaftsfreiheit (Art. 27 BV), die Rechtsgleichheit (Art. 8 Abs. 1 BV) oder Art. 13 lit. d der Interkantonalen Vereinbarung vom 25. November 1994 über das öffentliche Beschaffungswesen (IVöB; Beitritt des Kantons Zürich zur revidierten Fassung vom 15. März 2001 per 1. Januar 2004) verletzt sein soll.
5. In den Ausschreibungsunterlagen hat die Stadt Adliswil die Zuschlagskriterien wie folgt umschrieben: Preis (40%), Leistungsfähigkeit/Qualität (40%), Nachhaltigkeit (15%) und Lehrlingsausbildung (5%). Bei der Auswertung der vier verbliebenen Angebote erzielte die ortsansässige Beschwerdeführerin 1, welche die Kehrichtabfuhr der Stadt Adliswil bisher schon besorgt hatte, mit 98,18 Punkten das beste Resultat. Auch im Rahmen der hypothetischen "Schattenbewertung", in welche das ausgeschlossene Angebot der Beschwerdegegnerin miteinbezogen wurde, erzielte die Beschwerdeführerin 1 das beste Resultat; im Einzelnen ergab sich folgendes Bild:
Beschwerde-
führerin 1
Beschwerde-
gegnerin
Angebotspreis
34,76
40
Leistungsfähigkeit/Qualität
39,98
27,67
Nachhaltigkeit
15
2,53
Lehrlingsausbildung
5
0
Total
94,74
70,19
Das Verwaltungsgericht hat die "Schattenbewertung" der Angebote in verschiedener Hinsicht beanstandet und den Zuschlag an die Beschwerdeführerin 1 aufgehoben, weil nicht auszuschliessen sei, dass bei einer korrekten Bewertung der Zuschlag nicht dieser, sondern der Beschwerdegegnerin zu erteilen sei.
6. 6.1 Die Bewertung des Kriteriums "Angebotspreis" hatte die Stadt Adliswil in den Ausschreibungsunterlagen wie folgt umschrieben:
"Für das tiefste Angebot ist eine Maximalbewertung von 40 Punkten vorgesehen. Die Bandbreite wird vorgängig auf 50% festgelegt; für Angebote mit einem Preis von 150% des billigsten Angebots (Untergrenze: 10% unter ASTAG-Tarif, vgl. hinten Ziff. 12) werden also 0 Punkte vergeben. Angebote innerhalb dieser Bandbreite werden linear gemäss der prozentualen Abweichung zum niedrigsten Angebot bewertet.
Beispiel:
Beträgt der günstigste Angebotspreis CHF 100'000 kommt folgende Skala zur Anwendung
CHF 100'000 40 Punkte
CHF 110'000 32 Punkte
CHF 120'000 24 Punkte
CHF 130'000 16 Punkte
CHF 140'000 8 Punkte
CHF 150'000 0 Punkte"
6.2 Bei der effektiven Bewertung der Offertpreise ist die Stadt Adliswil alsdann wie folgt vorgegangen: Während sie das billigste Angebot mit 40 Punkten bewertete, erhielten die übrigen (teureren) Angebote linear abnehmend weniger Punkte. Die Bewertungsobergrenze, ab deren Erreichen ein Angebot keine Punkte mehr erhielt, wurde durch eine von den eingegangenen Angeboten unabhängige Berechnung ermittelt. Gestützt auf statistische Daten, welche der Nutzfahrzeugverband publizierte hatte, ging die Vergabebehörde davon aus, die von ihr nachgefragten Dienstleistungen müssten 1'477'423.52 Franken kosten. Diesen "ASTAG-Kalkulationswert" reduzierte sie alsdann um 10 Prozent auf 1'332'431.17 Franken (recte: 1'329'681.17 Franken) und verwendet diesen Wert zur Berechnung der Bewertungsobergrenze von 150 Prozent. Aufgrund dieses Vorgehens lag der Maximalpreis, ab dessen Erreichen keine Punkte mehr verteilt wurden, auf der Höhe von 1'998'646.76 Franken (recte: 1'994'521.75 Franken).
6.3 Das Verwaltungsgericht hat die Bewertung der Offerten unter dem Kriterium "Angebotspreis" im angefochtenen Entscheid als nicht sachgerecht erachtet. Die Vergabebehörde habe nicht auf das effektiv billigste Angebot abgestellt und das Vorgehen stehe im Widerspruch zu den Ausschreibungsbedingungen. Das Verwaltungsgericht entschied, richtigerweise müsse ein Angebot mit einem Preis, der 50 Prozent über jenem des billigsten Angebots der Beschwerdegegnerin liege, mit null Punkten bewertet werden. Es passte die Bewertungsskala entsprechend an, wodurch sich das Resultat der Beschwerdeführerin 1 unter dem Kriterium "Angebotspreis" auf 18,14 Punkte verschlechterte.
6.3.1 Die Kritik, welche die Beschwerdeführerinnen diesbezüglich am angefochtenen Entscheid üben, mag insoweit berechtigt sein, als die betreffenden Erwägungen teilweise zumindest missverständlich sind. So weisen die Beschwerdeführerinnen zu Recht darauf hin, dass die Beschwerdegegnerin im Rahmen der "Schattenberechnung" das Punktemaximum für das billigste Angebot erhalten hat. Diesen Umstand hat das Verwaltungsgericht jedoch nicht verkannt, sondern lediglich die (nicht gerade naheliegende) Berechnungsweise für die Bewertungsobergrenze missverstanden. Daraus vermögen die Beschwerdeführerinnen indessen nichts zu ihren Gunsten abzuleiten, hat das Verwaltungsgericht mit den betreffenden Ausführungen doch vorab beanstandet, dass die Vergabebehörde für die Bestimmung der Bewertungsobergrenze nicht auf das billigste Angebot abgestellt hat; insoweit hat es das Vorgehen der Stadt Adliswil durchaus richtig verstanden.
6.3.2 Wie gesehen hat die Stadt Adliswil den Maximalpreis, bei dessen Erreichen ein Angebot keine Punkte mehr erhielt, nicht ausgehend vom billigsten Angebot, sondern aufgrund einer Berechnung mit statistischem Zahlenmaterial bestimmt. Dabei ging sie davon aus, für die nachgefragten Dienstleistungen sei gemäss "ASTAG-Tarif" ein Preis in der Höhe von knapp 1,5 Mio. Franken zu bezahlen, obschon die eingegangen Angebote preislich zwischen 0,65 und 0,94 Mio. Franken lagen. Dergestalt setzte sie die Bewertungsobergrenze beim Kriterium "Angebotspreis" auf einen Betrag fest, der mit rund 2 Mio. Franken mehr als das Doppelte des teuersten eingegangenen Angebots und rund das Dreifache des billigsten Angebots ausmacht. Dieses Vorgehen führte dazu, dass die 40 zu vergebenden Punkte über eine wesentlich grössere "Bandbreite" (von rund 1,35 Mio. Franken) verteilt wurden, als wenn die Obergrenze 150 Prozent des billigsten Angebots betragen hätte. Es bedurfte so letztlich einer Preisdifferenz von knapp 34'000 Franken, um in der Bewertung einen Unterschied von einem einzigen Punkt zu erzielen. Das immerhin um 21 Prozent teurere Angebot der Beschwerdeführerin 1 erzielte deshalb lediglich 5,24 Punkte weniger als das billigste Angebot der Beschwerdegegnerin.
6.3.3 Ob für den streitigen Auftrag eine derart flache Preiskurve bereits an und für sich unzulässig wäre (vgl. <ref-ruling> E. 9.2 S. 327 f.), braucht hier nicht abschliessend beurteilt zu werden. Dies, weil das Verwaltungsgericht ohne Willkür annehmen konnte, die fragliche Bewertung stehe in offensichtlichem Widerspruch zu den Ausschreibungsbedingungen: In diesen wird klarerweise eine Bewertung in Aussicht gestellt, in welcher Angebote bis maximal zu einem Preis von 150 Prozent des billigsten Angebots - vorliegend also bis 971'527 Franken - Punkte erhalten. Dieses Bewertungsschema wird zudem durch ein Berechnungsbeispiel illustriert, in welchem sich der Preisrahmen für die Punkteverteilung allein und direkt aufgrund des günstigsten Angebots bestimmt (100'000 Franken = 40 Punkte, 150'000 Franken = 0 Punkte; vgl. E. 6.1). Auf die für die Bewertung effektiv verwendete Bewertungsobergrenze von 2 Mio. Franken wird demgegenüber in den einschlägigen Passagen mit keinem Wort hingewiesen; weder der Klammerbemerkung selbst, in welcher der "ASTAG-Tarif" kursorisch als "Untergrenze" erwähnt wird, noch Ziff. 12 der Ausschreibungsunterlagen, auf die am Rande verwiesen wird, lässt sich etwas Entsprechendes entnehmen. Ohne auf die Zulässigkeit der streitigen Preiskurve einzugehen, kann hier immerhin festgehalten werden, dass es der Vergabebehörde ein Leichtes gewesen wäre, in nachvollziehbarer Form auf die tatsächlich verwendete Bewertungsobergrenze hinzuweisen. Sie hat für deren Berechnung statistische Daten herangezogen, die offenbar von den offerierten Preisen unabhängig sind, so dass sie den Grenzwert zum Voraus genau hätte beziffern können, anstatt einfach mit einer (unverständlichen) Klammerbemerkung auf den "ASTAG-Tarif" zu verweisen.
6.3.4 Die Verwendung einer Skala mit einer derart hohen Bewertungsobergrenze führt zu wesentlich anderen Ergebnissen als in den Ausschreibungsunterlagen in Aussicht gestellt. Bei einem dem Berechnungsbeispiel entsprechenden Vorgehen beträgt die "Bandbreite" für die Punkteverteilung nicht 1,35 Mio., sondern rund 325'000 Franken, so dass bereits mit einer Preisdifferenz von 8'100 (anstatt 34'000) Franken ein Punkt zu gewinnen ist. Dieser Vergleich zeigt, dass die verwendete Skala offensichtlich nicht den Ausschreibungsunterlagen entspricht. Nach dem Gesagten hat das Verwaltungsgericht die Stadt Adliswil lediglich auf dem von ihr selber publizierten Bewertungsschema behaftet, weshalb weder das Willkürverbot noch die Gemeindeautonomie verletzt wurden. Weiter kann keine Rede davon sein, dass gegen das Transparenzgebot (Art. 1 Abs. 3 lit. c IVöB), den Grundsatz von Treu und Glauben (Art. 9 BV) oder den Vorrang des Bundesrechts (Art. 49 BV) verstossen worden wäre; eine Verletzung der Wirtschaftsfreiheit, des Anspruchs auf rechtliches Gehör und des Übereinkommens über das öffentliche Beschaffungswesen macht die Beschwerdeführerin 1 nicht rechtsgenüglich geltend.
7. 7.1 Das Verwaltungsgericht hat auch die Bewertung des Kriteriums der "Leistungsfähigkeit/Qualität" beanstandet. Insbesondere erachtete es als unzulässig, dass die Stadt Adliswil sich für die Bewertung der Angebote nicht an die Ausschreibungsunterlagen gehalten, sondern auf andere Unterkriterien abgestellt habe. Weiter habe die Vergabebehörde für den Zuschlag direkt die Ergebnisse aus der Präqualifikation herangezogen und keine Neubewertung der Angebote vorgenommen, so dass nicht zwischen Eignungs- und Zuschlagskriterien unterschieden worden sei. Sodann beanstandet das Verwaltungsgericht unter anderem, dass die wesentlich tiefere Bewertung des Angebots der Beschwerdegegnerin nur sehr pauschal begründet worden sei. Angesichts der dargestellten Mängel hielt es die Bewertung des Kriteriums der "Leistungsfähigkeit/Qualität" insgesamt für nicht haltbar.
7.2 Die Stadt Adliswil weist zwar die im angefochtenen Entscheid vorgetragene Kritik zurück. Ihre diesbezüglichen Vorbringen sind jedoch gänzlich im Appellatorischen verhaftet, so dass darauf mangels einer rechtsgenüglichen Rüge nicht weiter einzugehen ist, zumal in diesem Zusammenhang keine spezielle Konkordats- oder Verfassungsbestimmung genannt wird, die falsch angewendet worden sein soll (vgl. E. 2.4).
8. 8.1 Bezüglich des Kriteriums der "Nachhaltigkeit" hat das Verwaltungsgericht zunächst festgehalten, dass die Gesichtspunkte des Umweltschutzes in einem vertretbaren Mass in die Bewertung der Angebote eingeflossen seien und dass die Stadt Adliswil keine unzulässigen Unterkriterien verwendet habe. Anschliessend hat es betont, das blosse Einhalten von Mindestanforderungen gemäss Ausschreibungsunterlagen dürfe nicht als Zuschlagskriterium berücksichtigt werden. In diesem Zusammenhang wies es darauf hin, dass die Stadt Adliswil den Einsatz von Fahrzeugen vorausgesetzt habe, welche den Abgasgrenzwerten "EURO 4" genügen; deshalb könne ein Angebot, das insoweit bloss den Anforderungen entspreche, hierfür nicht bereits Punkte erhalten. Dabei hat das Verwaltungsgericht jedoch nicht verkannt, dass die Vergabebehörde im konkreten Fall das Übertreffen und nicht das Erfüllen der Mindestanforderung belohnt hat, indem es die Zusage aller Anbieter berücksichtigte, Fahrzeuge der Norm "EURO 5" einzusetzen.
8.2 Beanstandet hat das Verwaltungsgericht, dass die Stadt Adliswil unter Gesichtspunkten des Umweltschutzes zwar die Anfahrtswege der verschiedenen Anbieter, nicht aber die von diesen zurückgelegte Gesamtstrecke berücksichtigt hat; hinsichtlich Letzterer könnten sich aufgrund der Ladekapazität der einzelnen Fahrzeuge und der Organisation der Routen allenfalls Unterschiede ergeben. Der angefochtene Entscheid ist insoweit weder mit Blick auf die Gemeindeautonomie noch auf das Willkürverbot zu beanstanden:
8.2.1 Angesichts der mehrmals wöchentlich zu fahrenden "Touren" kann zwar vorliegend der vom jeweiligen Anbieter zurückzulegende Anfahrtsweg in einem gewissen Mass mitberücksichtigt werden. Es darf dabei aber nicht ausser Acht gelassen werden, dass die Lastwagen beim Einsammeln des Kehrichts immer wieder anhalten und anfahren müssen, wobei der Motor während der Zeit, in welcher das Fahrzeug stillsteht, weiterläuft oder gar für das Heben von Containern eingesetzt wird. Bei einer derartigen Fahrweise beträgt der Schadstoffausstoss erfahrungsgemäss ein Vielfaches der Menge, die beim Zurücklegen der gleichen Strecke in normaler Fahrt produziert würde (Urteil 2P.342/1999, in: ZBl 102/2001 S. 312, E. 4). Deshalb kann einerseits der (unbeladenen) Anfahrt hinsichtlich der gesamten resultierenden Umweltbelastung zum Vornherein nur untergeordnete Bedeutung zukommen und andererseits eine effizientere Erfüllung des eigentlichen Auftrags durchaus ins Gewicht fallen.
8.2.2 Eine Verletzung der Gemeindeautonomie ist auch nicht etwa darin zu sehen, dass das Verwaltungsgericht hinsichtlich einer Effizienzsteigerung das Zusammenlegen der beiden Routen thematisiert hat, auf denen der Kehricht bisher eingesammelt wurde. Die Frequenz, mit welcher der Kehricht abgeholt werden soll (hier zweimal pro Woche), muss die Gemeinde frei nach ihren Bedürfnissen bestimmen können. Das Verwaltungsgericht greift aber nicht in unzulässiger Weise in die Kompetenzen der Gemeinde ein, wenn es von ihr - unter Vorbehalt von besonderen Bedürfnissen - verlangt, den Anbietern eine gewisse unternehmerische Freiheit bei der Organisation der von diesen zu fahrenden Routen zuzugestehen. Daran ändert nichts, dass gegebenenfalls Anpassungen bezüglich des Zeitpunkts erforderlich werden, in dem die Einwohner gewöhnlich ihren Kehricht bereitzustellen haben. Vorliegend ist weder ersichtlich noch dargetan, inwiefern die Gemeinde ein schützenswertes Interesse an einer starren Beibehaltung der bisherigen Routen für die Kehrichtabfuhr hätte. Die Vermutung des Verwaltungsgerichts, der ortsansässigen Beschwerdeführerin 1 solle mittels dem Festhalten an den traditionellen Routen ein Vorteil verschafft werden, lässt sich nicht von der Hand weisen, zumal die Beschwerdeführerin 1 mit ihrem Fahrzeugpark offenbar nicht in der Lage ist, den Kehricht der ganzen Stadt Adliswil an einem einzigen Tag einzusammeln.
8.2.3 Ferner braucht nicht abschliessend beurteilt zu werden, ob sich die Stadt Adliswil allenfalls eine Verschiebung des Wochentags für die Kartonabfuhr gefallen lassen müsste. Das Verwaltungsgericht hat zwar festgehalten, die Gemeinde dürfte sich den entsprechenden Wünschen eines Anbieters nur aus triftigen Gründen widersetzen; weil die Stadt Adliswil aber gerade geltend macht, solche triftigen Gründe zu haben, ist sie durch die entsprechende Erwägung des angefochtenen Entscheids nicht eingeschränkt.
8.3 Das Verwaltungsgericht hat schliesslich beanstandet, dass für die Bewertung des Kriteriums der "Nachhaltigkeit" fast ausschliesslich das Umweltmanagement der Anbieter ausschlaggebend gewesen sei. Über die beiden Unterkriterien "ISO-Zertifizierung" einerseits und "Nachweis/Darlegung geringer Umweltbelastung" andererseits habe das Umweltmanagement letztlich knapp 87 Prozent des Kriteriums ausgemacht. Dieses theoretische Element erhalte so im Verhältnis zu den praktischen Umweltschutzaspekten wie dem Schadstoffausstoss der Fahrzeuge oder der zurückgelegten Fahrstrecke ein zu grosses Gewicht. Was die Beschwerdeführerinnen hiergegen vorbringen, ist rein appellatorischer Natur und nimmt auch keinen Bezug auf spezielle Konkordats- oder Verfassungsbestimmungen, so dass auf ihre entsprechenden Ausführungen nicht näher einzugehen ist. Gleich verhält es sich mit der Rüge der Stadt Adliswil, aufgrund der Vorgaben des Verwaltungsgerichts sei eine sachgerechte und rechtsgleiche Bewertung der eingereichten Angebote nicht möglich, weshalb ihr die Durchführung eines neuen Vergabeverfahrens zugestanden werden müsse.
9. Nach dem Gesagten sind die staatsrechtlichen Beschwerden unbegründet, soweit auf sie einzutreten ist.
Bei diesem Verfahrensausgang werden die Beschwerdeführerin 1 und die Stadt Adliswil, welche im vorliegenden Verfahren Vermögensinteressen im Sinne von Art. 156 Abs. 2 OG wahrnimmt (vgl. unveröffentlichtes Urteil 2P.148/2006 vom 2. Oktober 2006, E. 4; Urteil 2P.342/ 1999, in: ZBl 102/2001 S. 312, E. 6), kostenpflichtig (Art. 156 Abs. 1 und Abs. 2, Art. 153 sowie Art. 153a OG). Zudem haben sie die obsiegende Beschwerdegegnerin für den dieser im Zusammenhang mit dem bundesgerichtlichen Verfahren entstandenen Aufwand angemessen zu entschädigen (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Die Verfahren 2P.70/2006 und 2P.71/2006 werden vereinigt.
2. Die staatsrechtlichen Beschwerden werden abgewiesen, soweit auf sie einzutreten ist.
3. Die Gerichtsgebühr von insgesamt Fr. 20'000.-- wird den Beschwerdeführerinnen je zur Hälfte auferlegt.
4. Die Beschwerdeführerinnen haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren je mit Fr. 5'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 23. Februar 2007
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: