Sachverhalt:
A. Die Staatsanwaltschaft Zürich-Sihl führt eine Strafuntersuchung gegen X._ wegen des Verdachtes sexueller Handlungen mit Kindern und weiterer Delikte. Mit Verfügung des stellvertretenden Präsidenten des Bezirksgerichtes Zürich vom 7. Mai 2008 wurde der Angeschuldigte durch einen amtlichen Verteidiger verbeiständet. Einen vom Angeschuldigten dagegen erhobenen Rekurs wies das Obergericht des Kantons Zürich, III. Strafkammer, mit Beschluss vom 3. Juni 2008 rechtskräftig ab. Ein Gesuch des Angeschuldigten vom 4. November 2008 um Wechsel des Offizialverteidigers entschied der stellvertretende Präsident des Bezirksgerichtes Zürich am 2. Dezember 2008 abschlägig. Den dagegen erhobenen Rekurs wies das Obergericht des Kantons Zürich, III. Strafkammer, am 27. Januar 2009 ebenfalls ab.
B. Gegen den Beschluss des Obergerichtes vom 27. Januar 2009 gelangte X._ mit Beschwerde vom 9. März 2009 an das Bundesgericht. Er beantragt zur Hauptsache die Aufhebung des angefochtenen Entscheides.
Die Staatsanwaltschaft und das Obergericht liessen sich am 16. bzw. 26. März 2009 vernehmen, während das Bezirksgericht auf eine Stellungnahme ausdrücklich verzichtet hat und vom amtlichen Verteidiger keine Vernehmlassung eingegangen ist. Der Beschwerdeführer replizierte (nach erstreckter Frist) am 2. Juni 2009.

Erwägungen:
1. Beim angefochtenen Entscheid handelt es sich um eine selbstständig eröffnete strafprozessuale Zwischenverfügung, gemäss der ein Gesuch um Wechsel des Offizialverteidigers abgewiesen wird. Der Beschwerdeführer beanstandet, dem amtlichen Verteidiger seien diverse Pflichtversäumnisse anzulasten. Die Eintretensvoraussetzung des nicht wieder gutzumachenden Nachteils (<ref-law>) ist insofern grundsätzlich erfüllt (vgl. <ref-ruling> E. 2 S. 50 ff.; zur amtlichen Publikation bestimmtes Urteil 1B_7/2009 vom 16. März 2009 E. 1.2). Die übrigen Sachurteilsvoraussetzungen von <ref-law> geben zu keinen Bemerkungen Anlass.
2. Der Beschwerdeführer rügt eine Verletzung von Art. 29 Abs. 3 und Art. 32 Abs. 2 Satz 2 BV sowie Art. 6 Ziff. 3 EMRK und beantragt die Auswechslung des Offizialverteidigers.
2.1 Nach der Praxis des Bundesgerichtes zu Art. 29 Abs. 3 und <ref-law> (bzw. Art. 4 aBV) hat auch der amtlich verteidigte Angeschuldigte einen grundrechtlichen Anspruch auf sachkundige, engagierte und effektive Wahrnehmung seiner Parteiinteressen. Wird von den Behörden untätig geduldet, dass der amtliche Verteidiger seine anwaltlichen Berufs- und Standespflichten zum Nachteil des Angeschuldigten in schwerwiegender Weise vernachlässigt, kann darin eine Verletzung der von Verfassung und EMRK gewährleisteten Verteidigungsrechte liegen (<ref-ruling> E. 3d S. 198 f.; <ref-ruling> E. 2b/bb S. 51, je mit Hinweisen auf die Praxis der Strassburger Rechtsprechungsorgane).
2.2 Falls die genannten Anforderungen in der Person eines amtlichen Verteidigers nicht bzw. nicht mehr erfüllt sind, kann der Angeschuldigte nach der bundesgerichtlichen Rechtsprechung den Wechsel des amtlichen Verteidigers beantragen. Ein entsprechendes Gesuch ist jedoch nur (und immer dann) zu bewilligen, wenn aus objektiven Gründen eine sachgemässe Vertretung der Interessen des Angeschuldigten durch den Offizialverteidiger nicht mehr gewährleistet ist. Dass der Angeschuldigte ihm lediglich aus subjektiven Motiven das Vertrauen abspricht, reicht für einen verfassungsrechtlichen Anspruch auf Auswechslung des Offizialverteidigers nicht aus (<ref-ruling> E. 4b/aa S. 105; <ref-ruling> E. 3 S. 104, je mit Hinweisen). Dabei darf insbesondere der gute Wille des Angeschuldigten vorausgesetzt werden, mit seinem amtlichen Verteidiger konstruktiv zusammenzuarbeiten, zumal grundsätzlich dieser die Art und Weise der Verteidigung bestimmt und jedenfalls nicht bloss unkritisches Sprachrohr seines Mandanten ist (<ref-ruling> E. 4b/aa S. 30, 194 E. 3d S. 199; <ref-ruling> E. 4b/bb S. 105; Urteil 1P. 311/1999 vom 17. August 1999 E. 3a/bb).
2.3 Schwere Pflichtverletzungen des Offizialverteidigers können namentlich in krassen Frist- und Terminversäumnissen, mangelnder Sorgfalt bei der Vorbereitung von Einvernahmen und anderen Prozesshandlungen, fehlender Vorsorge für Stellvertretungen oder groben Unregelmässigkeiten bei der Rechnungsstellung liegen (vgl. <ref-ruling> E. 3d S. 199 f.; <ref-ruling> E. 2c-d S. 52 f., je mit Hinweisen). Auch bei der Prüfung, ob Verfahrens- und Beweisanträge im Interesse des Angeschuldigten zu stellen seien, hat der amtliche Verteidiger die nötige Sorgfalt anzuwenden. Dabei steht ihm jedoch ein erheblicher Ermessensspielraum zu. Als schwere Pflichtverletzung, welche eine Abberufung rechtfertigen würde, kann nur sachlich nicht vertretbares bzw. offensichtlich fehlerhaftes Prozessverhalten des Verteidigers in Frage kommen (Bundesgerichtsurteil 1P.311/1999 vom 17. August 1999 E. 3a/cc).
2.4 Im angefochtenen Entscheid wird Folgendes erwogen:
Der Beschwerdeführer habe im Rekursverfahren primär subjektive Gründe (wie angeblich fehlende "Empathie" seines amtlichen Verteidigers) für sein mangelndes Vertrauen in den Offizialanwalt geltend gemacht. Objektive Pflichtverletzungen des Rechtsvertreters seien nicht ersichtlich. Rechtzeitig vor einer Befragung des Angeschuldigten sei am 2. September 2008 eine Parteiinstruktion erfolgt. Der Vorwurf des Beschwerdeführers, es habe damals kein Gespräch stattgefunden, stehe im Widerspruch zu seiner eigenen Sachdarstellung. Dass der Verteidiger an der polizeilichen Einvernahme vom 3. September 2008 nur bis zum Abschluss der (anderthalb Stunden dauernden) Befragung zur Sache anwesend geblieben sei, könne nicht beanstandet werden, zumal eine Einvernahme zu den persönlichen Verhältnissen schon während einer früheren Befragung (am 8. April 2008) erfolgt sei. Dass der Verteidiger bei der Einvernahme vom 3. September 2008 "kaum ein Wort gesagt" habe, begründe ebenfalls kein Pflichtversäumnis. Der Verteidiger habe im Ermittlungs- und Untersuchungsverfahren in erster Linie über die Einhaltung der Verfahrensvorschriften bzw. die Wahrung der Parteirechte zu wachen. Soweit dies gewährleistet sei, bestehe kein Anlass zu Wortmeldungen des Verteidigers, und der Beschwerdeführer habe diesbezüglich auch keine Verfahrensfehler beanstandet.
Schon die erste kantonale Instanz habe dargelegt, dass das einmalige verspätete Erscheinen des Offizialanwaltes (bei einer Einvernahme vom 12. September 2008) nicht als schwerwiegende Verfehlung eingestuft werden könne; ein prozessualer Nachteil sei ebenso wenig ersichtlich, da laut Protokoll mit der Einvernahme erst nach Eintreffen des Verteidigers begonnen worden sei. Die nur beschränkt bzw. zögernd erfolgte Weitergabe von Aktenkopien durch den Verteidiger an den Beschwerdeführer stelle keine Pflichtverletzung dar. Es liege grundsätzlich im Ermessen des Offizialanwaltes zu beurteilen, welche persönlichen Aktenkopien für seinen Mandanten zu erstellen sind. Dies gelte besonders im vorliegenden Fall, zumal sich in den Akten kinderpornographisches Material befinde. Auch das Interesse an einer angemessenen Kostenbegrenzung könne eine Beschränkung der Aktenkopien rechtfertigen.
Der Vorwurf, der amtliche Verteidiger habe sich entgegen dem Wunsch des Beschwerdeführers nicht mit dessen Psychiaterin in Verbindung gesetzt, begründe ebenfalls kein Pflichtversäumnis. Da es hauptsächlich die Aufgabe des Anwaltes sei, die Verteidigungsstrategie festzulegen, liege es in seinem Ermessen zu entscheiden, wann er wen kontaktieren wolle. Analoges gelte für weitere Vorhaltungen des Beschwerdeführers (wonach sich der Offizialverteidiger zu wenig bei ihm gemeldet habe, oder dass sein Anwalt die Unterbrechung einer Einvernahme beantragt habe, um geschäftliche Telefonate zu erledigen).
2.5 Der Beschwerdeführer wiederholt über weite Strecken Vorbringen, mit denen sich bereits die kantonalen Instanzen ausführlich befasst haben. Dies gilt namentlich für die Vorwürfe, der amtliche Anwalt sei verschiedentlich telefonisch nicht erreichbar gewesen, das Treffen vom 2. September 2008 sei zeitlich zu knapp vor der polizeilichen Befragung vom 3. September 2008 erfolgt, der Offizialverteidiger habe vor dieser Einvernahme die Psychiaterin nicht kontaktiert und sei nur bis zum Abschluss der Befragung zur Sache anwesend geblieben, er sei bei einer weiteren Einvernahme (vom 12. September 2008) zu spät erschienen, oder er habe ihm, dem Beschwerdeführer, nicht sämtliche Akten zur Einsichtnahme zugestellt. Es kann offen bleiben, ob sich der Beschwerdeführer mit den betreffenden Erwägungen des angefochtenen Entscheides ausreichend auseinandersetzt und seine weitschweifige Eingabe insofern gesetzeskonform substanziiert ist (vgl. <ref-law>). Schwere Pflichtverletzungen des amtlichen Rechtsvertreters, welche aus verfassungsrechtlicher Sicht einen Verteidigerwechsel objektiv notwendig erscheinen liessen, sind jedenfalls nicht erkennbar. Diesbezüglich kann auf die zutreffenden Erwägungen der Vorinstanz verwiesen werden. Durch eine Verweigerung der Zusammenarbeit mit seinem amtlichen Rechtsvertreter kann der Beschwerdeführer (nach der oben dargelegten Praxis des Bundesgerichtes) keinen Wechsel des Offizialverteidigers gestützt auf Verfassung und EMRK erzwingen. Die zusätzlich erhobene Willkürrüge hat im vorliegenden Zusammenhang keine über das Dargelegte hinausgehende selbstständige Bedeutung.
3. Der Beschwerdeführer rügt sodann eine Verletzung des rechtlichen Gehörs (<ref-law>).
3.1 Zunächst beanstandet er (wie schon im kantonalen Rekursverfahren), dass er im erstinstanzlichen Verfahren keine Gelegenheit erhalten habe, auf die Stellungnahme seines Offizialverteidigers zu replizieren. Im angefochtenen Entscheid wird erwogen, dass ein allfälliger Verfahrensfehler spätestens im Rekursverfahren vor Obergericht geheilt worden wäre. Die Ansicht des Beschwerdeführers, ein entsprechender Verfahrensmangel könnte nicht geheilt werden, ist unzutreffend. Wie sich aus den Akten ergibt, erhielt der Beschwerdeführer im Rekursverfahren Gelegenheit, sich insbesondere zu den entscheidrelevanten Vorbringen seines amtlichen Verteidigers zu äussern. Die Gehörsrüge erweist sich als unbegründet.
3.2 Weiter beanstandet der Beschwerdeführer eine Verletzung seines verfassungsmässigen Anspruchs auf einen begründeten Entscheid. Wie sich aus den Akten ergibt, haben die kantonalen Instanzen die Entscheidmotive, die zur Ablehnung des beantragten Offizialverteidigerwechsels führten, ausführlich dargelegt. Dabei sind sie auch auf die wesentlichen relevanten Vorbringen des Beschwerdeführers ausreichend eingegangen. Sie mussten sich dabei nicht mit dessen sämtlichen Ausführungen ausdrücklich und im Einzelnen befassen (vgl. <ref-ruling> E. 3.1 S. 277; <ref-ruling> E. 3.2 S. 236, je mit Hinweisen). Insbesondere musste die Vorinstanz die im Lichte von Art. 29 Abs. 3 bzw. <ref-law> geprüfte Frage des Verteidigerwechsels nicht auch noch unter dem (unspezifischen) rechtlichen Gesichtspunkt des Willkürverbotes (<ref-law>) behandeln. Auch die betreffende Gehörsrüge ist unbegründet.
4. Der Beschwerdeführer rügt sodann eine Verletzung von <ref-law>, indem die kantonalen Gerichte in der Sache "vorbefasst" gewesen seien und in gleicher Besetzung entschieden hätten wie im rechtskräftig abgeschlossenen Verfahren betreffend amtliche Verbeiständung.
Es kann offen bleiben, ob sich der Beschwerdeführer mit den betreffenden Erwägungen des angefochtenen Entscheides ausreichend auseinandersetzt. Der blosse Umstand, dass der erstinstanzliche kantonale Richter im früheren (rechtskräftig abgeschlossenen) Verfahren den Offizialverteidiger bestellt habe, lässt ihn für die hier beurteilte Frage, ob eine Abberufung des Offizialverteidigers wegen angeblichen Prozessversäumnissen geboten erscheine, nicht als unzulässig vorbefasst bzw. befangen erscheinen. Analoges gilt für die kantonale Rekursinstanz. Auch aus den Entscheidbegründungen der kantonalen Gerichte ergeben sich keine Anhaltspunkte für die vom Beschwerdeführer behauptete Parteilichkeit. Seine Vermutung, die in einer Aktennotiz protokollierten telefonischen Aussagen des amtlichen Verteidigers könnten auf "Suggestivfragen" des erstinstanzlichen Richters zurückzuführen sein, beruht auf Spekulationen.
5. Schliesslich beanstandet der Beschwerdeführer, die Auflage von Gerichtskosten im angefochtenen Entscheid verletze seinen durch <ref-law> geschützten Anspruch auf unentgeltliche Prozessführung. Die Höhe der Gerichtsgebühr von Fr. 1'200.-- sei ausserdem "exorbitant" und willkürlich.
5.1 Im kantonalen Rekursverfahren wurde dem Beschwerdeführer die unentgeltliche Prozessführung in dem Sinne gewährt, als das Obergericht auf den Rekurs ohne Prozesskostenvorschuss eingetreten ist und das Rechtsmittel materiell behandelt hat. Im angefochtenen Entscheid wird dem Beschwerdeführer lediglich eine definitive Kostenbefreiung (auch für den Fall einer künftigen Einbringlichkeit bzw. des Wegfalls der geltend gemachten Mittellosigkeit des Beschwerdeführers) verweigert. Eine solche Regelung hält vor <ref-law> grundsätzlich stand. Die Verfassung verlangt (bei Bedürftigkeit des Gesuchstellers und Nichtaussichtslosigkeit seiner Rechtsbegehren) zwar die Befreiung vom Kostenvorschuss, nicht aber den definitiven Erlass von verursachten Gerichtskosten. Es ist nicht verfassungswidrig, diese Kosten bei einem nachträglichen Wegfall der finanziellen Bedürftigkeit (und nach Massgabe des kantonalen Prozessrechts) einzufordern (vgl. <ref-ruling> E. 2.4.2.2-2.4.2.3 S. 96 f.; <ref-ruling> E. 4a s. 6, 322 E. 2c S. 324, je mit Hinweisen).
5.2 Was die Höhe der Gerichtsgebühr betrifft, kann offen bleiben, ob diesbezüglich ein anfechtbarer letztinstanzlicher kantonaler Entscheid vorliegt (vgl. <ref-law>). Eine Gerichtsgebühr von Fr. 1'200.-- ist entgegen der vom Beschwerdeführer erhobenen Willkürrüge nicht unhaltbar. Die Vorinstanz stützt sich diesbezüglich auf den kantonalen Prozessgebührentarif. Der Beschwerdeführer legt nicht dar, inwiefern die Vorinstanz das kantonale Verfahrensrecht qualifiziert falsch angewendet hätte. Beim Rekursverfahren handelte es sich nicht um eine Bagatellsache. Insbesondere hatte die Vorinstanz eine komplexe Rekurseingabe des Beschwerdeführers mit zahlreichen Rügen zu prüfen. Auch materiell war der Streitgegenstand nicht unbedeutend: Im Falle eines Verteidigerwechsels hätte eine erhebliche Verzögerung und Komplizierung des Strafverfahrens wegen mutmasslichen sexuellen Kindesmissbrauchs sowie eine Verteuerung des Verfahrens gedroht. Die Willkürrüge erweist sich auch in diesem Punkt als unbegründet, soweit sie prozessual überhaupt zulässig erscheint.
6. Auf die weiteren Vorbringen des Beschwerdeführers kann mangels gesetzeskonformer Substanziierung nicht eingetreten werden (vgl. <ref-law>). Dies gilt namentlich für den Vorwurf der willkürlichen bzw. offensichtlich unrichtigen Sachverhaltsfeststellung durch die Vorinstanz.
7. Zusammenfassend ergibt sich, dass die Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann.
Der Beschwerdeführer stellt ein Gesuch um unentgeltliche Prozessführung. Da die gesetzlichen Voraussetzungen erfüllt sind (und insbesondere die finanzielle Bedürftigkeit des Gesuchstellers ausreichend glaubhaft gemacht wird), kann dem Begehren entsprochen werden (<ref-law>). Dem Ausgang des Verfahrens entsprechend ist keine Parteientschädigung zuzusprechen (<ref-law>). Da der Beschwerdeführer sich im Verfahren vor Bundesgericht nicht anwaltlich vertreten lässt, entfällt auch eine unentgeltliche Rechtsverbeiständung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit auf sie einzutreten ist.
2. Es werden keine Gerichtskosten erhoben und keine Parteientschädigung zugesprochen.
3. Dieses Urteil wird den Parteien, der Staatsanwaltschaft Zürich-Sihl, dem Bezirksgericht Zürich sowie dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 14. Juli 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Forster