Sachverhalt:
Sachverhalt:
A. X._ (geb. 1942) stand seit 1972 im Dienst der Stadt Luzern. Seine ursprünglich als Beamtenverhältnis ausgestaltete Stellung wurde mit der Einführung des neuen Personalreglements der Stadt Luzern vom 15. Juni 1998 (PRL, in Kraft getreten am 1. April 1999) in ein durch öffentlichrechtlichen Vertrag begründetes Dienstverhältnis umgewandelt. Am 12. Juli 1999 kündigte die Stadt Luzern dieses auf Ende Oktober 1999; X._ wurde zugleich ab 15. Juli 1999 von seinen Dienstpflichten freigestellt.
A. X._ (geb. 1942) stand seit 1972 im Dienst der Stadt Luzern. Seine ursprünglich als Beamtenverhältnis ausgestaltete Stellung wurde mit der Einführung des neuen Personalreglements der Stadt Luzern vom 15. Juni 1998 (PRL, in Kraft getreten am 1. April 1999) in ein durch öffentlichrechtlichen Vertrag begründetes Dienstverhältnis umgewandelt. Am 12. Juli 1999 kündigte die Stadt Luzern dieses auf Ende Oktober 1999; X._ wurde zugleich ab 15. Juli 1999 von seinen Dienstpflichten freigestellt.
B. Gegen die Kündigung erhob X._ Klage beim Verwaltungsgericht des Kantons Luzern. Neben einer Entschädigung von Fr. 60'512.50 beantragte er, die Nichtigkeit der Kündigung festzustellen; eventuell verlangte er eine Abgangsentschädigung von Fr. 1'229'085.-- sowie die Gewährung eines Kredits von Fr. 40'000.-- für eine Outplacement-Beratung und -Hilfe, subeventuell eine Entschädigung von Fr. 66'000.-- wegen rechtsmissbräuchlicher Kündigung. Überdies forderte er Änderungen seines Arbeitszeugnisses. Nach dem Beweisverfahren änderte er seine Rechtsbegehren und reduzierte sie teilweise.
Das Verwaltungsgericht des Kantons Luzern sprach X._ am 17. März 2004 in teilweiser Gutheissung der Klage einen Betrag von Fr. 35'747.10 zu und legte den Wortlaut des ihm neu auszustellenden Arbeitszeugnisses fest. Im Übrigen wies es die Klage ab.
Das Verwaltungsgericht des Kantons Luzern sprach X._ am 17. März 2004 in teilweiser Gutheissung der Klage einen Betrag von Fr. 35'747.10 zu und legte den Wortlaut des ihm neu auszustellenden Arbeitszeugnisses fest. Im Übrigen wies es die Klage ab.
C. Sowohl X._ als auch die Stadt Luzern führen gegen dieses Urteil staatsrechtliche Beschwerde.
Die Stadt Luzern beantragt zur Hauptsache, das Urteil des Verwaltungsgerichts des Kantons Luzern aufzuheben. Sie rügt eine Verletzung ihrer Autonomie und macht geltend, das Verwaltungsgericht habe zu Unrecht eine Verletzung von <ref-law> angenommen. Im Zusammenhang mit der Formulierung des Arbeitszeugnisses (Ziff. 2 des Urteilsdispositivs) beschwert sie sich wegen Willkür und wegen Verweigerung des rechtlichen Gehörs.
X._ beantragt, die Ziffern 3 und 4 des Urteilsdispositivs (Abweisung der Klage, soweit den zugesprochenen Betrag übersteigend [Ziff. 3]; dem Kläger auferlegte Kosten [Ziff. 4]) aufzuheben. Er erachtet die Kündigung als nichtig und rügt in verschiedener Hinsicht die Verletzung des Willkürverbots, des Grundsatzes von Treu und Glauben sowie seines Anspruchs auf rechtliches Gehör.
Das Verwaltungsgericht des Kantons Luzern und X._ beantragen, die staatsrechtliche Beschwerde der Stadt Luzern abzuweisen, soweit darauf einzutreten sei.
Denselben Antrag stellt das Verwaltungsgericht des Kantons Luzern zur staatsrechtlichen Beschwerde X._s; die Stadt Luzern beantragt, auf dessen Beschwerde nicht einzutreten, eventuell sie abzuweisen, soweit darauf einzutreten sei.
In einer unaufgefordert eingereichten Eingabe vom 6. September 2004 äussert sich die Stadt Luzern zu einzelnen Ausführungen in der zu ihrer Beschwerde eingereichten Vernehmlassung des Verwaltungsgerichts.

Das Bundesgericht zieht in Erwägung:
Das Bundesgericht zieht in Erwägung:
1. 1.1 Beide staatsrechtlichen Beschwerden richten sich gegen dasselbe Urteil, beziehen sich auf den gleichen Lebenssachverhalt und werfen zusammenhängende Rechtsfragen auf. Es rechtfertigt sich deshalb, die Verfahren zu vereinigen und in einem Urteil zu erledigen (vgl. <ref-ruling> E. 1, mit Hinweisen).
1.2 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid, der sich auf kantonales (bzw. kommunales) Recht stützt und gegen den als eidgenössisches Rechtsmittel einzig die staatsrechtliche Beschwerde zulässig ist (Art. 84 Abs. 2, Art. 86 und 87 OG).
I. Beschwerde 2P.104/2004 der Stadt Luzern
I. Beschwerde 2P.104/2004 der Stadt Luzern
2. 2.1 Abgesehen von hier nicht zutreffenden Ausnahmen hat die staatsrechtliche Beschwerde rein kassatorische Wirkung. Soweit die Stadt Luzern mehr verlangt als die Aufhebung des angefochtenen Entscheides, kann darauf nicht eingetreten werden (<ref-ruling> E. 1.5, S. 176). Dies gilt auch für die Eingabe der Stadt Luzern vom 6. September 2004; da kein zweiter Schriftenwechsel (Art. 93 Abs. 3 OG) angeordnet wurde, ist diese unbeachtlich.
2.2 Die Stadt Luzern geniesst im Bereich des Personalwesens und namentlich bei der Regelung ihrer öffentlichrechtlichen Arbeitsverhältnisse Autonomie (vgl. § 2 Abs. 2 in Verbindung mit § 2 Abs. 1 und § 1 lit. e des im Zeitpunkt der Entlassung in Kraft stehenden Gesetzes vom 13. September 1988 über das öffentlich-rechtliche Dienstverhältnis [Personalgesetz] [aPG/LU]; heute: § 1 Abs. 4 und § 2 lit. c des Gesetzes vom 26. Juni 2001 über das öffentlich-rechtliche Arbeitsverhältnis [Personalgesetz; PG/LU], in Kraft seit 1. Januar 2003); dies gilt grundsätzlich auch mit Bezug auf die Formulierung eines Arbeitszeugnisses. Sie kann sich insoweit mit staatsrechtlicher Beschwerde dagegen zur Wehr setzen, dass eine kantonale Behörde in einem Rechtsmittel- oder Klageverfahren ihre Prüfungsbefugnis überschreitet oder die den betreffenden Sachbereich ordnenden kommunalen, kantonalen oder bundesrechtlichen Vorschriften falsch anwendet. Sie kann in diesem Rahmen auch geltend machen, die kantonalen Behörden hätten die Tragweite eines Grundrechts verkannt und dieses zu Unrecht als verletzt betrachtet. Soweit es um die Handhabung von eidgenössischem oder kantonalem Verfassungsrecht geht, prüft das Bundesgericht das Vorgehen der kantonalen Behörden frei, sonst nur auf Willkür hin (<ref-ruling>, E. 2.2 S.141, mit Hinweis).
2.2 Die Stadt Luzern geniesst im Bereich des Personalwesens und namentlich bei der Regelung ihrer öffentlichrechtlichen Arbeitsverhältnisse Autonomie (vgl. § 2 Abs. 2 in Verbindung mit § 2 Abs. 1 und § 1 lit. e des im Zeitpunkt der Entlassung in Kraft stehenden Gesetzes vom 13. September 1988 über das öffentlich-rechtliche Dienstverhältnis [Personalgesetz] [aPG/LU]; heute: § 1 Abs. 4 und § 2 lit. c des Gesetzes vom 26. Juni 2001 über das öffentlich-rechtliche Arbeitsverhältnis [Personalgesetz; PG/LU], in Kraft seit 1. Januar 2003); dies gilt grundsätzlich auch mit Bezug auf die Formulierung eines Arbeitszeugnisses. Sie kann sich insoweit mit staatsrechtlicher Beschwerde dagegen zur Wehr setzen, dass eine kantonale Behörde in einem Rechtsmittel- oder Klageverfahren ihre Prüfungsbefugnis überschreitet oder die den betreffenden Sachbereich ordnenden kommunalen, kantonalen oder bundesrechtlichen Vorschriften falsch anwendet. Sie kann in diesem Rahmen auch geltend machen, die kantonalen Behörden hätten die Tragweite eines Grundrechts verkannt und dieses zu Unrecht als verletzt betrachtet. Soweit es um die Handhabung von eidgenössischem oder kantonalem Verfassungsrecht geht, prüft das Bundesgericht das Vorgehen der kantonalen Behörden frei, sonst nur auf Willkür hin (<ref-ruling>, E. 2.2 S.141, mit Hinweis).
3. Die Stadt Luzern wirft dem Verwaltungsgericht vor, die Garantie des rechtlichen Gehörs zu Unrecht auf eine Vertragskündigung angewandt zu haben, welche keinen hoheitlichen Verwaltungsakt, sondern eine rechtsgeschäftliche Willenserklärung ohne Verfügungscharakter darstelle. Die erste hoheitliche Entscheidung treffe im Streitfall nicht die Verwaltung, sondern das Gericht. Die Vorschriften des Verwaltungsverfahrensgesetzes kämen hier nur in gewissen Punkten, nicht aber bezüglich des rechtlichen Gehörs zur Anwendung. Auch <ref-law> sei, was den Anspruch auf eine vorherige Äusserungsmöglichkeit anbelange, grundsätzlich nur in hoheitlichen Verwaltungs- und in Gerichtsverfahren anwendbar. Die gegenteilige Auffassung des Verwaltungsgerichts, wonach die Verwaltung vor jeder rechtsgeschäftlichen Erklärung, sei sie öffentlichrechtlicher oder privatrechtlicher Natur, ein eigentliches formelles Verfahren (mit vorgängiger Orientierung und Stellungnahme sowie eventuellen weiteren Beweiserhebungen) durchzuführen hätte, wäre mit unüberwindbaren praktischen Schwierigkeiten verbunden. Die im Personalreglement gewählte Vertragskonstruktion beruhe auf der Gleichordnung von Staat und Privaten. Für eine "Sonderbehandlung des öffentlichen Personalrechts" bestehe kein Grund. Im Übrigen wäre die teilweise Gutheissung der Klage (Entschädigung im Sinne von <ref-law>) selbst dann ungerechtfertigt, wenn die Stadt Luzern zur vorherigen Anhörung des Betroffenen verpflichtet gewesen wäre, denn die Verletzung des rechtlichen Gehörs sei im Verfahren vor Verwaltungsgericht, das über freie Kognition verfügt habe, geheilt worden. Schliesslich enthalte auch das vom Verwaltungsgericht formulierte Arbeitszeugnis krass unrichtige Aussagen.
3. Die Stadt Luzern wirft dem Verwaltungsgericht vor, die Garantie des rechtlichen Gehörs zu Unrecht auf eine Vertragskündigung angewandt zu haben, welche keinen hoheitlichen Verwaltungsakt, sondern eine rechtsgeschäftliche Willenserklärung ohne Verfügungscharakter darstelle. Die erste hoheitliche Entscheidung treffe im Streitfall nicht die Verwaltung, sondern das Gericht. Die Vorschriften des Verwaltungsverfahrensgesetzes kämen hier nur in gewissen Punkten, nicht aber bezüglich des rechtlichen Gehörs zur Anwendung. Auch <ref-law> sei, was den Anspruch auf eine vorherige Äusserungsmöglichkeit anbelange, grundsätzlich nur in hoheitlichen Verwaltungs- und in Gerichtsverfahren anwendbar. Die gegenteilige Auffassung des Verwaltungsgerichts, wonach die Verwaltung vor jeder rechtsgeschäftlichen Erklärung, sei sie öffentlichrechtlicher oder privatrechtlicher Natur, ein eigentliches formelles Verfahren (mit vorgängiger Orientierung und Stellungnahme sowie eventuellen weiteren Beweiserhebungen) durchzuführen hätte, wäre mit unüberwindbaren praktischen Schwierigkeiten verbunden. Die im Personalreglement gewählte Vertragskonstruktion beruhe auf der Gleichordnung von Staat und Privaten. Für eine "Sonderbehandlung des öffentlichen Personalrechts" bestehe kein Grund. Im Übrigen wäre die teilweise Gutheissung der Klage (Entschädigung im Sinne von <ref-law>) selbst dann ungerechtfertigt, wenn die Stadt Luzern zur vorherigen Anhörung des Betroffenen verpflichtet gewesen wäre, denn die Verletzung des rechtlichen Gehörs sei im Verfahren vor Verwaltungsgericht, das über freie Kognition verfügt habe, geheilt worden. Schliesslich enthalte auch das vom Verwaltungsgericht formulierte Arbeitszeugnis krass unrichtige Aussagen.
4. 4.1 Der Umfang des Anspruchs auf rechtliches Gehör wird zunächst durch die kantonalen Verfahrensvorschriften umschrieben. Dabei prüft das Bundesgericht im Verfahren der staatsrechtlichen Beschwerde die Anwendung kantonalen Gesetzesrechts nur auf Willkür hin. Unabhängig davon greifen die aus <ref-law> folgenden Verfahrensregeln zur Sicherung des rechtlichen Gehörs Platz. Ob diese missachtet worden sind, prüft das Bundesgericht frei (vgl. <ref-ruling> E. 2, mit Hinweisen).
Willkürlich ist ein Entscheid nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5a S. 70).
4.2 Das Verwaltungsgericht geht mit der Stadt Luzern davon aus, dass die Kündigung des als verwaltungsrechtlicher Vertrag konzipierten Dienstverhältnisses zwischen der Stadt Luzern und X._ nach den einschlägigen Rechtsgrundlagen von Stadt und Kanton Luzern nicht als "Entscheid" (d.h. als Verfügung), sondern als "andere behördliche Anordnung" im Sinne von § 8 Abs. 1 des luzernischen Gesetzes vom 3. Juli 1972 über die Verwaltungsrechtspflege (Verwaltungsrechtspflegegesetz; VRG/LU) zu treffen sei.
Die Stadt Luzern schliesst daraus, dass die Kündigung insoweit ein rechtsgeschäftlicher, nicht ein hoheitlicher Akt sei, weshalb gemäss § 8 Abs. 2 VRG/LU auch der in § 46 VRG/LU geregelte Anspruch auf Gewährung des rechtlichen Gehörs nicht anwendbar sei. Die bundesgerichtliche Rechtsprechung habe bisher noch nie einen verfassungsrechtlichen Anspruch auf vorgängige Anhörung in einem nicht hoheitlichen Verfahren statuiert.
4.3 Das fragliche Dienstverhältnis wird vom einschlägigen kommunalen Recht ausdrücklich als öffentlichrechtlich bezeichnet. Diese Qualifikation ist auch von keiner Seite bestritten.
4.4 Der Anspruch auf rechtliches Gehör im Sinne einer vorherigen Orientierung und Gewährung einer Äusserungsmöglichkeit gilt für Verfahren, die in eine (hoheitliche) Verfügung münden. Die Kündigung eines öffentlichrechtlichen Dienstverhältnisses durch den öffentlichen Arbeitgeber ist nach den einschlägigen Rechtsordnungen selbst dann, wenn es auf einem öffentlichrechtlichen Vertrag beruht, in der Regel als (anfechtbare) Verfügung ausgestaltet, um dem Betroffenen entsprechende Verfahrensgarantien zu gewähren und ihm den Beschwerdeweg zu öffnen (vgl. etwa Art. 13 Abs. 3 des Bundespersonalgesetzes vom 24. März 2000; Art. 22 f. des bernischen Gesetzes vom 5. November 1992 über das öffentliche Dienstrecht in Bezug auf das Angestelltenverhältnis; Art. 82 f. des St. Galler Staatsverwaltungsgesetzes vom 16. Juni 1994 [dazu: GVP 1995 Nr. 3]). Der Betroffene hat in diesem Fall Anspruch auf vorherige Anhörung sowie auf Begründung der Kündigungsverfügung, und er kann durch erfolgreiche Anfechtung der Kündigung den Weiterbestand des Dienstverhältnisses oder Ersatzansprüche erwirken, während ihm bei rechtsgeschäftlicher Ausgestaltung zur Geltendmachung von Ansprüchen nur der weniger einfache Weg der Klage bleibt (vgl. dazu Minh Son Nguyen, La fin des rapports de service, in: Personalrecht des öffentlichen Dienstes, Hrsg. Peter Helbling/Tomas Poledna, Bern 1999, S. 457 ff.).
Wohl ist das Gemeinwesen, selbst wenn es vertraglich oder privatrechtlich handelt, an die grundrechtlichen Schranken und an die Gebote rechtsstaatlichen Handelns gebunden (<ref-law>; <ref-ruling> E. 4c S. 90, mit Hinweisen). Wo es aber nach den einschlägigen Vorschriften zulässigerweise als Vertragspartner auftritt und Rechtsbeziehungen in den Formen des Vertrages ordnet, besteht grundsätzlich kein Anspruch des (privaten) Vertragspartners auf vorheriges rechtliches Gehör vor vertragsändernden oder -auflösenden Erklärungen des Gemeinwesens.
4.5 Eine besondere Sach- und Interessenlage besteht hingegen bei öffentlichrechtlichen Dienstverhältnissen, deren Inhalt durch das Gemeinwesen selber hoheitlich normiert wird und die gleichzeitig formell als Vertragsverhältnis ausgestaltet werden. Das Gemeinwesen tritt hier, trotz der an sich vertraglichen Grundlage des Dienstverhältnisses, als Hoheitsträger auf. Zugleich kann die unfreiwillige Beendigung des Dienstverhältnisses durch eine Kündigungserklärung des Gemeinwesens, auch wenn sie formell als nicht hoheitliche Ausübung eines Gestaltungsrechts erscheint, in existenzielle Interessen des privaten Vertragspartners eingreifen. Das Gemeinwesen bleibt in einem solchen Fall, wie das Verwaltungsgericht in zulässiger Weise annehmen durfte, bei der Ausübung seines Kündigungsrechts an die Grundsätze staatlichen Handelns gebunden (vgl. Art. 5 und Art. 35 Abs. 2 BV). Das Verwaltungsgericht hat denn auch in Würdigung des städtischen Personalreglements und seiner Materialien mit überzeugender Begründung erwogen, dass dieses durch die Unterstellung des Dienstverhältnisses unter ein (öffentlichrechtliches) vertragsrechtliches Regime elementare Verfahrensvorschriften, wie etwa das rechtliche Gehör, nicht ausschalten wollte. Diese Erwägungen halten vor dem Willkürverbot stand. Die Rüge der Stadt Luzern, das Verwaltungsgericht habe zu Unrecht auf eine Verletzung des Gehörsanspruchs von X._ erkannt, erweist sich deshalb schon kraft dieser willkürfreien Auslegung des städtischen Personalreglements als unbegründet.
4.6 Als dem Gemeinwesen auferlegte allgemeine verfassungsrechtliche Schranke für die Ausübung des Kündigungsrechts fällt namentlich das Gebot der Verhältnismässigkeit in Betracht. Der Betroffene soll nach Möglichkeit zuerst durch Ermahnung und Androhung der Kündigung angehalten werden, sein Verhalten zu bessern, bevor zur Auflösung des Dienstverhältnisses geschritten wird. Wegen der einschneidenden Wirkung, welche mit der Auflösung des Dienstverhältnisses verbunden sein kann, durfte das Verwaltungsgericht nach dem Gesagten aber auch zulässigerweise davon ausgehen, die Stadt Luzern sei zudem zur vorherigen Anhörung des Betroffenen verpflichtet gewesen. Das war der Stadt Luzern umso eher zuzumuten, als sie ihre Kündigung im Hinblick auf die für den Fall missbräuchlicher Kündigung vorgesehenen Entschädigungsansprüche (vgl. Art. 13 PRL in Verbindung mit Art. 336 f. OR) begründen musste (das Kündigungsschreiben vom 12. Juli 1999 enthielt denn auch eine - wenn auch relativ knappe - Begründung), was wiederum - im Sinne einer korrekten Sachverhaltsabklärung - eine vorherige Anhörung des Betroffenen geboten hätte. Wenn das Verwaltungsgericht bei der Beurteilung der Rechtmässigkeit der Kündigung und der damit zusammenhängenden Entschädigungsansprüche die dem Gemeinwesen bei öffentlichrechtlichen Dienstverhältnissen auferlegten Schranken im dargelegten Sinne berücksichtigte, liegt darin keine Verletzung der Gemeindeautonomie durch unrichtige Handhabung von Grundrechtsgarantien. Durch die im nachträglichen Verfahren vor dem Richter bestehende Äusserungsmöglichkeit wurden die dargestellten Mängel sodann nicht beseitigt; insbesondere kann nicht von einer Heilung der Gehörsverletzung gesprochen werden, nachdem das angerufene Gericht die Kündigung als solche nicht aufheben, sondern nur eine (beschränkte) Entschädigung zusprechen konnte. Die erhobene Autonomiebeschwerde vermag in diesem Punkt nicht durchzudringen.
4.7 Dass der Begriff der "missbräuchlichen Kündigung" im Sinne des Personalreglementes vom Verwaltungsgericht willkürlich angewendet worden wäre, wird von der Stadt Luzern nicht geltend gemacht; ebenso wenig beanstandet sie die Höhe der zugesprochenen Entschädigung als verfassungswidrig, weshalb auf diese Fragen nicht einzugehen ist.
4.7 Dass der Begriff der "missbräuchlichen Kündigung" im Sinne des Personalreglementes vom Verwaltungsgericht willkürlich angewendet worden wäre, wird von der Stadt Luzern nicht geltend gemacht; ebenso wenig beanstandet sie die Höhe der zugesprochenen Entschädigung als verfassungswidrig, weshalb auf diese Fragen nicht einzugehen ist.
5. 5.1 Die Stadt Luzern erachtet zwei Passagen des X._ neu auszustellenden Arbeitszeugnisses als derart krass unrichtig und für Dritte täuschend, dass sie es als unzumutbar erachtet, dieses Zeugnis zu unterschreiben.
5.2 Die von Lehre und Praxis entwickelten Grundsätze, denen ein Arbeitszeugnis nach <ref-law> zu entsprechen hat - insbesondere die Wahrheitspflicht - sind vom Verwaltungsgericht zutreffend dargestellt worden; die Stadt Luzern übt denn auch zu Recht keine Kritik daran. Die Anwendung dieser Grundsätze kann vom Bundesgericht im Verfahren der staatsrechtlichen Beschwerde nur auf Willkür hin überprüft werden; vorbehalten bleiben Verfahrensmängel wie die Verweigerung des rechtlichen Gehörs.
5.3 Die erste der kritisierten Aussagen bescheinigt X._ berufliche Kompetenz ("qualifizierte[r] Abteilungsleiter") und hält fest, dass er "seine Aufgaben zuverlässig und verantwortungsbewusst wahrnahm".
In Anbetracht der Tatsache, dass die Stadt Luzern die Qualifikation von X._ und die Zuverlässigkeit seiner Aufgabenerfüllung im Verfahren vor Verwaltungsgericht vehement bestritten und diesbezüglich auch Beweisanträge gestellt hat, wäre das Verwaltungsgericht gestützt auf <ref-law> verpflichtet gewesen, beweismässig näher abzuklären, ob eine solche vorbehaltlos positive Aussage sachlich zu vertreten war. Indem es dies unterliess, hat es den Anspruch der Stadt Luzern auf Gewährung des rechtlichen Gehörs verletzt.
Bei diesem Ergebnis kann offen bleiben, inwiefern weitere Formulierungen ebenfalls zu beanstanden wären, da das Verwaltungsgericht diesbezüglich ohnehin neu zu urteilen hat, soweit es den Parteien - was ihnen zuzumuten wäre - nicht noch gelingt, sich auf eine beidseits akzeptable Formulierung zu einigen.
Beschwerde 2P.118/2004 von X._
Beschwerde 2P.118/2004 von X._
6. 6.1 Das Verwaltungsgericht hat die Kündigung trotz der festgestellten Verletzung des rechtlichen Gehörs als rechtsbeständig und insbesondere nicht als nichtig beurteilt.
X._ macht unabhängig von der Verletzung seines Anspruches auf rechtliches Gehör eine Verletzung des Willkürverbotes und des Grundsatzes von Treu und Glauben geltend (Beschwerde Ziff. 4). Im Besonderen rügt er die Unverhältnismässigkeit und Rechtsmissbräuchlichkeit der Kündigung; beide Beschwerdegründe ruft er ausschliesslich im Zusammenhang mit dem Willkürverbot an (Beschwerde Ziff. 25-31). Diese qualifizierten Fehler haben seines Erachtens zudem die Nichtigkeit der Kündigung zur Folge.
6.2 Für die Frage, ob ein Betroffener ein rechtlich geschütztes Interesse (Art. 88 OG) an der verfassungsrechtlichen Überprüfung einer ihm gegenüber ausgesprochenen Kündigung hat, stellt das Bundesgericht auf die einschlägige kantonale Regelung ab. Sieht diese keine inhaltlichen Voraussetzungen für die Kündigung vor, ist die Legitimation des Gekündigten zu verneinen (<ref-ruling>, 126 I 81; Urteil 2P.233/2000 vom 22. März 2001 E.1b und c); den Umstand, dass ein kantonales Verwaltungsgericht in seiner Praxis verlangt, dass die zuständige Behörde ihr Ermessen pflichtgemäss auszuüben oder sachliche Gründe zu beachten habe, hat das Bundesgericht in verschiedenen Entscheiden als unerheblich erachtet (insb. Urteile 2P.233/2000 vom 22. März 2001 E. 2b/c; 2P.157/2000 vom 10. Oktober 2000 E. 2b; 1P.794/1999 vom 25. April 2000, E. 1a/b). Dass das Gemeinwesen bei der Ausübung seines Kündigungsrechts die Grundsätze rechtsstaatlichen Handelns zu beachten hat und seine Ermessensbetätigung von kantonalen Rechtsmittelinstanzen daran gemessen werden kann, begründet für sich allein noch keine Legitimation des Betroffenen zur staatsrechtlichen Beschwerde.
Soweit X._ daher das Vorliegen eines ausreichenden Kündigungsgrundes bestreiten will, ist davon auszugehen, dass nach den einschlägigen kommunalen Bestimmungen die Zulässigkeit einer (ordentlichen) Kündigung - vorbehältlich der Entschädigungspflicht bei "missbräuchlicher Kündigung" - nicht von bestimmten materiellen Voraussetzungen abhängt und sich der Betroffene dagegen nicht mit staatsrechtlicher Beschwerde zur Wehr setzen kann. Der Umstand, dass das Verwaltungsgericht die Kündigung wegen Verletzung des rechtlichen Gehörs als rechtswidrig bzw. rechtsmissbräuchlich eingestuft und dem Betroffenen deswegen eine Entschädigung zugesprochen hat, kann nicht dazu führen, dass die materielle Berechtigung der Kündigung trotz fehlender gesetzlicher Schutznorm unter dem Gesichtswinkel des Willkürverbotes geprüft werden müsste.
Soweit X._ daher das Vorliegen eines ausreichenden Kündigungsgrundes bestreiten will, ist davon auszugehen, dass nach den einschlägigen kommunalen Bestimmungen die Zulässigkeit einer (ordentlichen) Kündigung - vorbehältlich der Entschädigungspflicht bei "missbräuchlicher Kündigung" - nicht von bestimmten materiellen Voraussetzungen abhängt und sich der Betroffene dagegen nicht mit staatsrechtlicher Beschwerde zur Wehr setzen kann. Der Umstand, dass das Verwaltungsgericht die Kündigung wegen Verletzung des rechtlichen Gehörs als rechtswidrig bzw. rechtsmissbräuchlich eingestuft und dem Betroffenen deswegen eine Entschädigung zugesprochen hat, kann nicht dazu führen, dass die materielle Berechtigung der Kündigung trotz fehlender gesetzlicher Schutznorm unter dem Gesichtswinkel des Willkürverbotes geprüft werden müsste.
6.3 6.3.1 Unabhängig von der Legitimation in der Sache selbst kann mit staatsrechtlicher Beschwerde die Verletzung solcher Verfahrensgarantien gerügt werden, deren Missachtung eine formelle Rechtsverweigerung darstellt. Nicht zu hören sind dabei aber Rügen, die im Ergebnis auf eine Überprüfung des angefochtenen Entscheides abzielen, so etwa die Behauptung, Beweisanträge seien wegen Unerheblichkeit oder willkürlicher antizipierter Beweiswürdigung abgelehnt worden oder die Begründung des angefochtenen Entscheids sei unvollständig oder zu wenig differenziert ausgefallen und setze sich nicht mit sämtlichen von den Parteien erhobenen Argumenten auseinander (Urteil 2P.116/ 2001 vom 29. August 2001 E. 3b, mit Hinweisen). Ein in der Sache nicht legitimierter Beschwerdeführer kann deshalb weder die Beweiswürdigung kritisieren noch geltend machen, die Begründung sei materiell unzutreffend (Urteil 2P.204/2000 vom 10. November 2000 E. 2e, mit Hinweisen; vgl. <ref-ruling> E. 3c S. 313).
6.3.2 Das Verwaltungsgericht hat angenommen, die Stadt Luzern habe X._ aus sachlich vertretbarem Grund gekündigt; es sieht diesen in der Qualität seiner Arbeitsleistung im Zusammenhang mit dem Projekt "Strassenrechnung". X._ rügt diesbezüglich sowohl willkürliche, insbesondere offensichtlich ungenügende Sachverhaltsfeststellung als auch Verweigerung des rechtlichen Gehörs, indem auf von ihm vorgebrachte Behauptungen, Argumente und Beweisanträge ungerechtfertigt nicht eingegangen worden sei. Er kritisiert namentlich auch, dass das Verwaltungsgericht bloss aufgrund eines einzigen, von ihm bestrittenen Kündigungsgrundes auf sachliche Rechtfertigung der Kündigung geschlossen habe, ohne seine 27-jährige Anstellungsdauer einer fairen Gesamtwürdigung zu unterziehen. Diese Argumente (Beschwerde Ziff. 35-43) betreffen die materielle Würdigung des Falles, weshalb nach dem oben Ausgeführten darauf nicht einzutreten ist.
6.4 Zu prüfen bleibt der Einwand, die ausgesprochene Kündigung hätte wegen der ihr anhaftenden Mängel als nichtig behandelt werden müssen. Nichtigkeitsgründe sind jederzeit und von sämtlichen rechtsanwendenden Behörden - d.h. auch im Rechtsmittelverfahren - von Amtes wegen zu beachten (<ref-ruling> E. 2) und damit frei zu prüfen. Ob auch diese Prüfung grundsätzlich ein rechtlich geschütztes Interesse im Sinne von Art. 88 OG voraussetzt, kann offen bleiben, da der Einwand der Nichtigkeit unbegründet ist.
6.4.1 Damit Nichtigkeit anzunehmen ist, muss eine Verfügung einen besonders schweren Mangel aufweisen und der Mangel offensichtlich oder zumindest leicht erkennbar sein und darf die Nichtigkeit die Rechtssicherheit nicht ernsthaft gefährden (<ref-ruling> E. 3a/aa, mit Hinweisen; Ulrich Häfelin/Georg Müller, Allgemeines Verwaltungsrecht, 4. Aufl., Zürich 2002, a.a.O., N 956). Als Nichtigkeitsgründe fallen namentlich schwerwiegende Zuständigkeitsfehler, schwerwiegende Verfahrens- und Formfehler sowie schwerwiegende inhaltliche Mängel in Betracht (Häfelin/Müller, a.a.0. N 959 ff.). Die Verweigerung des rechtlichen Gehörs ist zwar ein gravierender Rechtsfehler, gilt im Verwaltungsrecht aber gleichwohl regelmässig nicht als Nichtigkeitsgrund (Häfelin/Müller, a.a.0. N 965 ff. [e contrario]; Max Imboden/René A. Rhinow, Schweizerische Verwaltungsrechtsprechung, 5. A., Basel und Stuttgart, 1976, Nr. 40 B/V/b; René Rhinow/Beat Krähenmann, Schweizerische Verwaltungsrechtsprechung, Ergänzungsband, Basel und Frankfurt, 1990, Nr. 40 B/V/b; Max Imboden, Der nichtige Staatsakt, Zürich 1944, S. 132)
6.4.2 Soweit X._ die Nichtigkeit der Kündigung aus der unterbliebenen vorherigen Androhung und Anhörung ableiten will, ist zu bemerken, dass das einschlägige Personalreglement ein solches Vorgehen nicht ausdrücklich vorschreibt und die Kündigung als blosses Gestaltungsrecht vorsieht. Eine solche Ordnung verstösst nicht geradezu offensichtlich gegen verfassungsmässige Rechte. Der Stadt Luzern kann deshalb keine derart grobe offensichtliche Rechtsverletzung vorgeworfen werden, dass als Rechtsfolge Nichtigkeit in Frage käme.
6.4.3 Auch das zuvor unklare, eher inkonsequente und unter dem Gesichtspunkt von Treu und Glauben zwiespältige Verhalten des X._ vorgesetzten Z._s erscheint angesichts der glaubhaft von beiden Seiten als unbefriedigend empfundenen Zusammenarbeit nicht als derart gravierend, dass es positiv schutzwürdiges Vertrauen bei X._ hätte begründen und im Zusammenhang mit dem Verfahrensfehler zur Nichtigkeit der Kündigung führen können.
6.4.3 Auch das zuvor unklare, eher inkonsequente und unter dem Gesichtspunkt von Treu und Glauben zwiespältige Verhalten des X._ vorgesetzten Z._s erscheint angesichts der glaubhaft von beiden Seiten als unbefriedigend empfundenen Zusammenarbeit nicht als derart gravierend, dass es positiv schutzwürdiges Vertrauen bei X._ hätte begründen und im Zusammenhang mit dem Verfahrensfehler zur Nichtigkeit der Kündigung führen können.
7. Im bundesgerichtlichen Verfahren nicht angefochten sind die vom Verwaltungsgericht zugesprochene Entschädigung nach <ref-law> sowie die vom Verwaltungsgericht verneinte Frage, ob X._ sich darüber hinaus auch auf den obligationenrechtlichen Kündigungsschutz bei Krankheit (<ref-law>) berufen könne.
7. Im bundesgerichtlichen Verfahren nicht angefochten sind die vom Verwaltungsgericht zugesprochene Entschädigung nach <ref-law> sowie die vom Verwaltungsgericht verneinte Frage, ob X._ sich darüber hinaus auch auf den obligationenrechtlichen Kündigungsschutz bei Krankheit (<ref-law>) berufen könne.
8. Zusammengefasst erweist sich die Beschwerde X._s als unbegründet, soweit darauf einzutreten ist.
8. Zusammengefasst erweist sich die Beschwerde X._s als unbegründet, soweit darauf einzutreten ist.
8. Zusammengefasst erweist sich die Beschwerde X._s als unbegründet, soweit darauf einzutreten ist.
9.1 9.1.1 Die Stadt Luzern obsiegt teilweise, nämlich mit Bezug auf das Zeugnis. Im Übrigen erweist sich ihre Beschwerde als unbegründet. Da es sich in der Sache um eine vermögensrechtliche Streitigkeit handelt, hat die Stadt Luzern eine (reduzierte) Gerichtsgebühr zu bezahlen. Ein Betrag von Fr. 2'000.-- erscheint angemessen.
9.1.2 X._ unterliegt mit seiner Beschwerde in vollem Umfang; lediglich soweit die Stadt Luzern unterliegt, obsiegt er teilweise. Eine Gerichtsgebühr von Fr. 8'000.-- ist angesichts des Streitwertes angemessen.
9.2 Der Stadt Luzern, die als grösseres Gemeinwesen über einen eigenen Rechtsdienst verfügt, ist nach der Praxis keine Parteientschädigung zuzusprechen. X._ unterliegt mit seiner Beschwerde voll, obsiegt aber im Verfahren der Stadt Luzern teilweise. Diese hat ihm daher für das bundesgerichtliche Verfahren eine (reduzierte) Parteientschädigung von Fr. 2'000.-- auszurichten.
9.3 Anlass zur Korrektur des verwaltungsgerichtlichen Kostenspruchs besteht angesichts der insgesamt relativ geringen Bedeutung des Obsiegens der Stadt Luzern nicht.

Demnach erkennt das Bundesgericht:
Demnach erkennt das Bundesgericht:
1. Die Verfahren 2P.104/2004 und 2P.118/2004 werden vereinigt.
1. Die Verfahren 2P.104/2004 und 2P.118/2004 werden vereinigt.
2. Die staatsrechtliche Beschwerde der Stadt Luzern wird, soweit darauf einzutreten ist, teilweise gutgeheissen und Ziffer 2 des Dispositivs des Urteils des Verwaltungsgerichts des Kantons Luzern vom 17. März 2004 aufgehoben. Im Übrigen wird die Beschwerde abgewiesen.
2. Die staatsrechtliche Beschwerde der Stadt Luzern wird, soweit darauf einzutreten ist, teilweise gutgeheissen und Ziffer 2 des Dispositivs des Urteils des Verwaltungsgerichts des Kantons Luzern vom 17. März 2004 aufgehoben. Im Übrigen wird die Beschwerde abgewiesen.
3. Die Beschwerde von X._ wird abgewiesen, soweit darauf einzutreten ist.
3. Die Beschwerde von X._ wird abgewiesen, soweit darauf einzutreten ist.
4. Der Stadt Luzern wird eine Gerichtsgebühr von Fr. 2'000.-- auferlegt, X._ eine solche von Fr. 8'000.--.
4. Der Stadt Luzern wird eine Gerichtsgebühr von Fr. 2'000.-- auferlegt, X._ eine solche von Fr. 8'000.--.
5. Die Stadt Luzern hat X._ für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
5. Die Stadt Luzern hat X._ für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
6. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Luzern schriftlich mitgeteilt.
Lausanne, 14. März 2005
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: