Abgangsentschädigung, hat sich ergeben: A.- X._, geboren am ******, trat im Jahre 1969 in die Dienste der Radio Schweiz AG ein, wo er im Flug- und Seefunk tätig war. Auf den 1. Januar 1988 wechselte er zu den Fernmeldediensten der Generaldirektion PTT, da die Radio Schweiz AG weitgehend aufgelöst wurde. In der Folge ging der Flug- und Seefunkdienst von der Telecom PTT auf die Swisscom über, die im Herbst 1997 beschloss, diesen Bereich einzustellen bzw. auf eine private Trägerschaft zu übertragen. Die Geschäftsstelle Network Services der Swisscom AG wurde beauftragt, Massnahmen im Zusammenhang mit dem dadurch bedingten Personalabbau auszuarbeiten. An einer im März 1998 durchgeführten Informationsveranstaltung wurde X._, dessen Stelle im Zuge der geplanten Umstrukturierungen aufgehoben werden sollte, auf entsprechende Frage hin vom Personalverantwortlichen - in Anwesenheit des Direktors der genannten Geschäftsstelle - bestätigt, dass auch beim Wechsel zu einer Bundesstelle eine Abgangsentschädigung ausgerichtet werde. Nachdem das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation (UVEK) mit Schreiben vom 15. Mai 1998 X._ einen Anstellungsvertrag als Dienstchef im Generalsekretariat/Dienst für besondere Aufgaben unterbreitet hatte, kündigte er seine Anstellung bei der Swisscom auf den 31. Juli 1998. Im Kündigungsschreiben vom 25. Mai 1998 ersuchte er ausdrücklich darum, die "vorgesehene Abgangsentschädigung mit der letzten Lohnabrechnung auszubezahlen". Die Swisscom AG bestätigte die Auflösung des Arbeitsverhältnisses am 26. Juni 1998 und teilte X._ gleichzeitig mit, die Abgangsentschädigung von Fr. 196'236.-- werde mit dem letzten Gehalt vom Juli 1998 überwiesen. Auf Grund einer Intervention der internen Revisionsstelle zahlte die Swisscom AG in der Folge die Abgangsentschädigung nicht aus. Sie informierte X._ mit Schreiben vom 3. August 1998 darüber, dass die Auszahlung einer Abgangsentschädigung gemäss Ziffer 10.1 der vorliegend anwendbaren Richtlinien 96/2000 der Telecom PTT auf die Aufgabe der Erwerbstätigkeit, den Übertritt in die Privatwirschaft und die Aufnahme einer selbstständigen Erwerbstätigkeit beschränkt sei; diese Aufzählung sei abschliessend; bei einem Wechsel zu einer Bundesstelle könne deshalb keine Abgangsentschädigung ausgerichtet werden. Die X._ erteilte, anderslautende Auskunft sei "rechtlich gesehen ... eine 'Falschauskunft einer amtlichen Behörde'", welche die Swisscom AG jedoch nicht zu binden vermöge, da er gestützt darauf noch keine nicht rückgängig zu machenden Dispositionen getroffen habe. B.- Die Swisscom AG, Geschäftsstelle Network Services, verfügte am 1. Oktober 1998, X._ werde die in Aussicht gestellte Abgangsentschädigung in der Höhe von Fr. 196'236.-- wegen fehlender Rechtsgrundlage nicht ausbezahlt. Auf die hiergegen erhobene Beschwerde trat die Swisscom AG, Headquarters, am 4. Juni 1999 nicht ein. X._ focht den Entscheid mit Eingabe vom 12. Juli 1999 bei der Eidgenössischen Personalrekurskommission an. Diese hat die Beschwerde am 31. Mai 2000 teilweise gutgeheissen, den Beschwerdeentscheid der Swisscom AG, Headquarters, vom 4. Juni 1999 aufgehoben und die Swisscom AG verpflichtet, X._ eine Abgangsentschädigung von Fr. 125'000.-- auszubezahlen, zuzüglich 5 % Zins seit dem 1. August 1998. Im Weiteren auferlegte sie ihm 3/8 der Verfahrenskosten von Fr. 3'200.-- (Spruch- und Schreibgebühren), nämlich Fr. 1'200.--, und sprach ihm eine reduzierte Parteientschädigung von Fr. 4'500.-- zu. C.- X._ hat am 30. Juni 2000 Verwaltungsgerichtsbeschwerde beim Bundesgericht eingereicht mit dem Antrag, den Entscheid der Eidgenössischen Personalrekurskommission vom 31. Mai 2000 aufzuheben, insoweit ihm die Abgangsentschädigung im Umfang von Fr. 71'236.-- nicht zugesprochen, insoweit ihm Verfahrenskosten auferlegt und insoweit ihm nicht die volle Parteientschädigung ausgerichtet worden seien. Die Swisscom AG sei zu verpflichten, ihm den Betrag von Fr. 196'236.-- plus Zins zu 5 % seit 1. August 1998 zu bezahlen, plus vollen Parteikostenersatz für alle Instanzen. Die Eidgenössische Personalrekurskommission hat mit Schreiben vom 19. Juli 2000 auf eine Vernehmlassung verzichtet. Die Swisscom AG beantragt, die Verwaltungsgerichtsbeschwerde kostenfällig abzuweisen, soweit darauf einzutreten sei; angesichts der Komplexität der Streitsache sei der Swisscom AG ferner eine angemessene Parteientschädigung zuzusprechen.