Fernmeldegebühren, hat sich ergeben:
A.- Ab Januar 1996 verfügte O._ an der B._strasse in X._ über einen Telefonanschluss. Nachdem er die Gebührenrechnung für den Dezember 1996 beanstandet hatte, stellte ihm die Direktion Zürich der Telecom PTT (nachfolgend: Direktion Zürich) am 28. Januar 1997 einen "Fragebogen über den Telefonverkehr" zu. Am 1. April 1997 sandte O._ den ausgefüllten Fragebogen zurück. Darin beanstandete er neu auch die Rechnung für Januar 1997; den Teilbetrag, den er nicht akzeptiere, bezifferte er für beide Monate auf insgesamt Fr. 4'000. --.
Die Direktion Zürich nahm in der Folge verschiedene Abklärungen vor. Sie erstellte einen kundenbezogenen, vollständigen Gebührenauszug und veranlasste am 18. Juli 1997 eine Überprüfung des Telefonanschlusses durch den Störungsdienst. Weil O._ in der Zwischenzeit umgezogen war, konnte keine vollständige Kontrolle mehr erfolgen; soweit eine solche noch möglich war, liessen sich jedoch keine Manipulationsspuren feststellen. Die Direktion Zürich kam deshalb zum Schluss, dass die taxierten Verbindungen von O._s Telefonapparat aus hergestellt worden seien, und hielt an den ausgestellten Rechnungen fest (Schreiben vom 17. September 1997).
B.- Am 21. November 1997 erliess die Swisscom (vormals: Telecom PTT) antragsgemäss eine anfechtbare Verfügung; sie hielt fest, dass die Gesprächstaxen für die Zeit vom 1. Dezember 1996 bis 31. Januar 1997 Fr. 4'559. 10 ausmachten, und verpflichtete O._ zur Bezahlung des ausstehenden Teilbetrags von Fr. 2'744. 15. Hiergegen erhob O._ (entsprechend der Rechtsmittelbelehrung) Beschwerde bei der Generaldirektion PTT. Er beantragte, ihm sei die bei Anschlusseinrichtung hinterlegte Kaution zurückzuerstatten, abzüglich der Gebühren für die anerkannten Gespräche. Die Swisscom AG - inzwischen als selbständige Aktiengesellschaft ausgestaltet und Rechtsnachfolgerin der PTT-Betriebe im Bereich der Telekommunikation - wies die Beschwerde am 17. Mai 1999 ab.
C.- Am 17. Juni 1999 hat O._ hiergegen Verwaltungsgerichtsbeschwerde beim Bundesgericht eingereicht mit dem Antrag, den angefochtenen Entscheid aufzuheben. Die Swisscom AG schliesst auf Abweisung der Beschwerde.
Am 29. November 1999 ersuchte der Instruktionsrichter die Swisscom AG, bei welcher der Beschwerdeführer das von ihm verwendete Telefongerät (NP-80C mit "schnurlosem Handapparat") gekauft hatte, um Auskunft zu technischen Fragen. Zum Antwortschreiben, welches die Swisscom AG am 16. Dezember 1999 einreichte, nahm der Beschwerdeführer am 9. Februar 2000 Stellung.

Das Bundesgericht zieht in Erwägung:
1.- a) Am 1. Januar 1998 sind die bisherigen PTT- Betriebe aufgeteilt worden: Neben der schweizerischen Post (Art. 2 Abs. 2 des Postgesetzes vom 30. April 1997 [PG; SR 783. 0]) wurde die Swisscom AG gegründet (vgl. Art. 1 des Bundesgesetzes vom 30. April 1997 über die Organisation der Telekommunikationsunternehmung des Bundes [TUG; SR 784. 11]). Diese Aktiengesellschaft des öffentlichen Rechts ist grundsätzlich dem Obligationenrecht unterstellt (Art. 4 TUG); Streitigkeiten zwischen ihr und der Kundschaft fallen dementsprechend unter die Zivilgerichtsbarkeit (Art. 19 Abs. 1 TUG). Die Swisscom AG übernimmt die Rechte und Pflichten der PTT-Betriebe aus den Verwaltungsrechtsverhältnissen, die gestützt auf die Fernmelde- und Rundfunkgesetzgebung begründet worden sind, und regelt diese neu durch privatrechtliche Verträge (Art. 24 Abs. 1 TUG). Auf Verfügungen, die vor dem 1. Januar 1998 erlassen worden sind, und Beschwerdeverfahren, welche zu diesem Zeitpunkt noch hängig sind, ist das bisherige Recht anwendbar (Art. 24 Abs. 3 TUG). Gemäss diesem haben die Organe der Telecom PTT (bzw. übergangsrechtlich der Swisscom AG als deren Rechtsnachfolgerin) Verfügungskompetenz (vgl. insb. Art. 15 Abs. 2 der Verordnung vom 22. Juni 1970 zum PTT-Organisationsgesetz [VPTT-OG] in der Fassung vom 12. Mai 1993).
b) Der angefochtene Entscheid ist von der letzten Instanz einer autonomen eidgenössischen Anstalt (bzw. der hier übergangsrechtlich als solche auftretenden Swisscom AG) gefällt worden und stützt sich auf öffentliches Recht des Bundes (Art. 97 Abs. 1 OG in Verbindung mit Art. 5 Abs. 1 VwVG, Art. 98 lit. d OG und Art. 60 des Fernmeldegesetzes vom 21. Juni 1991 [aFMG]); er unterliegt keinem der Ausschlussgründe der Art. 99 ff. OG, weshalb die Verwaltungsgerichtsbeschwerde zulässig ist. Auf die frist- und formgerechte Eingabe des gemäss Art. 103 lit. a OG legitimierten Beschwerdeführers ist einzutreten.
c) Mit der Verwaltungsgerichtsbeschwerde kann die Verletzung von Bundesrecht, einschliesslich Überschreitung oder Missbrauch des Ermessens, sowie die unrichtige oder unvollständige Feststellung des rechtserheblichen Sachverhalts gerügt werden (Art. 104 lit. a und b OG). Das Bundesgericht prüft von Amtes wegen und frei, ob Bundesrecht verletzt wurde; eine gewisse Zurückhaltung drängt sich jedoch in technischen Fragen auf, in welchen die vorinstanzlichen
Behörden über die besseren Kenntnisse verfügen (<ref-ruling> E. 1b S. 409, mit Hinweis).
2.- Der Abonnent eines Telefonanschlusses schuldet den PTT-Betrieben u.a. Verbindungsgebühren für die Benutzung des Telefonnetzes (Art. 38 Abs. 1 lit. d aFMG in Verbindung mit Art. 47 Abs. 1 lit. b und Art. 50 ff. der Verordnung vom 25. März 1992 über Fernmeldedienste [aFDV]); die geschuldeten Gebühren werden von den PTT-Betrieben aufgrund deren Aufzeichnungen berechnet (Art. 41 Abs. 1 aFMG). Dabei ist der Abonnent für die erlaubte oder unerlaubte Benützung seines Netzanschlusses durch Dritte verantwortlich (Art. 28 aFDV). Die Rechnungen der PTT-Betriebe gelten von Gesetzes wegen als richtig; Voraussetzung ist jedoch, dass sie die nötigen technischen und administrativen Abklärungen vorgenommen haben, ohne dass diese Anhaltspunkte für eine fehlerhafte Aufzeichnung oder Rechnungsstellung lieferten (Abs. 2). Durch diese gesetzliche Vermutung ist nicht ausgeschlossen, dass Abonnenten die Fehlerhaftigkeit von Aufzeichnungen und Rechnungen nachweisen können. Die bundesgerichtliche Rechtsprechung verlangt dafür keinen strikten Beweis; es genügt, wenn die Unrichtigkeit mit an Sicherheit grenzender Wahrscheinlichkeit dargetan wird.
a) Der Beschwerdeführer macht vorab geltend, die Telecom PTT (bzw. Swisscom) habe es pflichtwidrig unterlassen, rechtzeitig abzuklären, ob - auf mechanischem oder elektronischem Weg - von aussen auf seine Telefonleitung eingewirkt worden sei. Ihm ist insoweit zuzustimmen, als die Überprüfung durch den Störungsdienst in der Tat (zu) spät erfolgt ist. Die Verantwortung hierfür trägt er jedoch selbst: Die Direktion Zürich hatte ihn aufgefordert, den zugestellten "Fragebogen über den Telefonverkehr" innert zweier Wochen zurückzusenden, und gleichzeitig angekündigt, andernfalls betrachte sie seine Beanstandung als erledigt. Dennoch hat der Beschwerdeführer über zwei Monate damit zugewartet, das Formular zu retournieren. Die Swisscom durfte deshalb bis zu dessen Eintreffen am 3. April 1997 davon ausgehen, dass er die umstrittenen Gebührenrechnungen nunmehr anerkenne. Unter diesen Umständen kann der Beschwerdeführer heute nicht rügen, die vorgenommene technische Kontrolle sei unvollständig gewesen. Der Direktion Zürich verblieben, nachdem sie von seinem Insistieren Kenntnis hatte, lediglich vier Wochen, um eine Überprüfung zu veranlassen - dies weil er bereits Ende April 1997 in eine andere Wohnung umzog. Nachdem der Beschwerdeführer einen "unerlaubten Zugriff Dritter" auf "Aussenanlagen, wie Verteiler, Freileitungen usw. " vermutete, wäre er deshalb gehalten gewesen, auf den bevorstehenden Umzug hinzuweisen. So hätte die Direktion Zürich Gelegenheit gehabt, seinen Telefonanschluss und die verwendeten Geräte zusammen zu kontrollieren. Im Übrigen hat er - entgegen den anderslautenden Behauptungen - Manipulationen Dritter erstmals am 23. Juni 1997 (implizit) geltend gemacht. Dies veranlasste die Direktion Zürich, am 18. Juli 1997 die Anlagen vor Ort zu überprüfen; sie hatte die Vornahme weiterer Abklärungen zuvor mit Schreiben vom 1. Juli 1997 angekündigt. Damit hat die Direktion Zürich innert nützlicher Frist auf die (erstmals konkreteren) Vorbringen des Beschwerdeführers reagiert. Dieser hat es primär eigenen Versäumnissen zuzuschreiben, dass zum damaligen Zeitpunkt keine vollständige Überprüfung der technischen Anlagen mehr möglich war.
b) Der Beschwerdeführer bringt vor, sein Telefonanschluss sei "mit an grösster Sicherheit grenzender Wahrscheinlichkeit. .. angezapft" worden; deshalb lasse sich aus dem von der Direktion Zürich erstellten Gebührenauszug nichts ableiten. Er vermag diese Behauptung jedoch durch keinerlei Indizien zu bekräftigen. Die technischen und administrativen Abklärungen der Swisscom haben keine Hinweise auf Manipulationen durch Dritte ergeben. Auch die Vermutung, mittels einer Funkverbindung seien (von ausserhalb seiner Wohnräume) Gespräche über seinen Telefonanschluss geführt worden, liess sich nicht erhärten. Es ist zwar - wie die Instruktionsmassnahmen des Bundesgerichts ergeben haben - theoretisch nicht völlig ausgeschlossen, dass ein Dritter mittels eines (normgleichen) Funktelefons auf die Basisstation des Beschwerdeführers greifen könnte. Ein derartiger Missbrauch ist jedoch höchst unwahrscheinlich: Das vom Beschwerdeführer verwendete Telefongerät entspricht dem CT2- Standard des "European Telecommunications Standards Institute" (ETSI), welcher auf digitaler Technologie basiert. Entgegen der Vermutung des Beschwerdeführers handelt es sich nicht um ein (ganz einfaches) analoges Gerät, bei welchem - gemäss dem ins Recht gelegten Zeitungsartikel (NZZ Orbit, 23. September 1997) - eine gewisse Missbrauchsgefahr bestehen würde. Im Übrigen muss ein mittels Funkverbindung funktionierender Handapparat, bevor damit telefoniert werden kann, bei der Basisstation (NP-80C) "angemeldet" werden; dazu ist offenbar mindestens eine Taste an dieser selbst zu betätigen und das Funktelefon gleichzeitig "in die Nähe der Basisstation" zu bringen (vgl. Kapitel 5 der Bedienungsanleitung). Unter diesen Umständen kann keine Rede davon sein, dass die Unrichtigkeit der beanstandeten Rechnungen bzw. ein unbefugter Zugriff auf den Anschluss des Beschwerdeführers (mit an Sicherheit grenzender Wahrscheinlichkeit) nachgewiesen ist.
c) Schliesslich macht der Beschwerdeführer noch eine Verletzung des Anspruchs auf rechtliches Gehör geltend (Art. 4 aBV; vgl. <ref-ruling> E. 2b S. 137); die Vorinstanz habe sich mit seinen Einwänden nicht auseinandergesetzt. Auch diese Rüge ist nicht stichhaltig: Der angefochtene Entscheid geht ausführlich auf die Vorbringen des Beschwerdeführers ein. Dieser präzisierte denn auch nicht weiter, welchen konkreten Einwänden (nur) ungenügend Rechnung getragen worden sein soll.
3.- Die Verwaltungsgerichtsbeschwerde erweist sich nach dem Gesagten als unbegründet. Dem Verfahrensausgang entsprechend wird der Beschwerdeführer kostenpflichtig (Art. 156 Abs. 1 in Verbindung mit Art. 153 und Art. 153a OG). Es ist keine Parteientschädigung auszurichten (Art. 159 OG).

Demnach erkennt das Bundesgericht:
1.- Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2.- Die Gerichtsgebühr von Fr. 2'000. -- wird dem Beschwerdeführer auferlegt.
3.- Dieses Urteil wird den Parteien schriftlich mitgeteilt.
_
Lausanne, 8. März 2000
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: