Sachverhalt:
A. X._ (geb. 1946), dipl. Architekt ETH/SIA, war seit dem 1. Januar 1997 beim Hochbauamt des Kantons Zug als Projektleiter angestellt. Am 30. September 2005 wurde er im Rahmen einer Fürsorgerischen Freiheitsentziehung in die Psychiatrische Klinik Oberwil und anschliessend in die Psychiatrische Universitätsklinik Zürich eingewiesen. Gleichentags erstattete der Kantonsbaumeister gegen X._ Strafanzeige wegen Drohung.
Am 5. Oktober 2005 verfügte die Baudirektion des Kantons Zug die sofortige Freistellung X._s von seinen Arbeitsverpflichtungen. Am 20. Januar 2006 fand ein Gespräch zwischen dem Rechtsvertreter von X._, dem Kantonsbaumeister und der Leiterin des Personalamtes statt. Mit Schreiben der Baudirektion vom 1. März 2006 teilte die Baudirektion X._ mit, dass man unter den gegebenen Umständen eine Auflösung des Arbeitsverhältnisses in Betracht ziehen müsse. Aufgrund der bekannten und aktenkundigen Vorfälle sei eine weitere Zusammenarbeit mit ihm nicht mehr möglich und ein weniger weit reichender Schluss wäre nicht angemessen. Mit Schreiben vom 4. März 2006 liess X._ die Baudirektion auffordern, sämtliche Gründe im Einzelnen anzugeben, weshalb sie die Auflösung des Arbeitsverhältnisses beabsichtige und weshalb eine weniger weitgehende Massnahme für sie nicht in Frage komme. Sodann ersuchte er um Zustellung sämtlicher Akten, auf welche die Baudirektion sich bei ihrem anstehenden Entscheid stützen wolle. Mit Schreiben vom 16. März 2006 präzisierte die Baudirektion die Gründe für die in Aussicht genommene Kündigung und verdeutlichte, dass die Verhaltensweise von X._ dem Arbeitsverhältnis die Vertrauensgrundlage entzogen habe. Der Schritt hänge nicht mit den Arbeitsleistungen X._s zusammen, weshalb auch allfällige mildere Massnahmen von vornherein keinen Sinn machen würden. Mit Eingabe vom 13. April 2006 liess sich X._ zu den im Schreiben der Baudirektion vom 16. März 2006 vorgebrachten Gründen vernehmen. Am 29. April 2006 ergänzte er seine Stellungnahme nochmals, nachdem das Untersuchungsrichteramt Zug das Strafverfahren gegen X._ betreffend Drohung mit Verfügung vom 21. April 2006 eingestellt hatte. Die Baudirektion verfügte am 16. Mai 2006, das Arbeitsverhältnis mit X._ werde unter Einhaltung der gesetzlichen Kündigungsfrist von vier Monaten per 30. September 2006 aufgelöst.
Gegen diese Verfügung liess X._ am 12. Juni 2006 Beschwerde beim Regierungsrat des Kantons Zug einreichen. Er beantragte, es sei die Missbräuchlichkeit der Auflösung des Arbeitsverhältnisses festzustellen. Weiter sei ihm eine Entschädigung im Umfang von neun Monatslöhnen inklusive Zulagen und 13. Monatslohn pro rata zuzusprechen. Mit Entscheid vom 1. Mai 2007 wies der Regierungsrat die Beschwerde ab. Er erwog im Wesentlichen, die Akteneinsicht sei vollumfänglich und rechtzeitig, nämlich vor Erlass der angefochtenen Verfügung vom 16. Mai 2006, gewährt worden. Die Kündigung beruhe auf Gründen, die von einem gewissen Gewicht seien, nämlich auf dem durch das Verhalten von X._ verursachten zunehmenden Vertrauensverlust zwischen ihm und seinen Vorgesetzten. Das Verwaltungsgericht des Kantons Zug schützte den abschlägigen Entscheid des Regierungsrates mit Urteil vom 31. Oktober 2008.
B. X._ hat gegen das Urteil des Verwaltungsgerichts wegen Verletzung von §§ 10, 13 und 14 des Gesetzes des Kantons Zug vom 1. September 1994 über das Arbeitsverhältnis des Staatspersonals (Personalgesetz; BGS 154.21) und des Willkürverbots (<ref-law>) beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Er beantragt, der Kanton Zug sei zu verpflichten, dem Beschwerdeführer den Betrag von Fr.111'816.45 als Entschädigung i.S. von § 14 Personalgesetz zu bezahlen, zuzüglich 5 % Zins ab 16. Mai 2006, unter Kosten- und Entschädigungsfolgen.
C. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde. Die Finanzdirektion des Kantons Zug beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Der angefochtene Entscheid, ein Endentscheid einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d, Art. 90 BGG), betrifft ein öffentlich-rechtliches Arbeitsverhältnis, d.h. eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law>. Der Beschwerdeführer macht Forderungen im Betrag von insgesamt Fr. 111'816.45 geltend. Es handelt sich um eine vermögensrechtliche Streitigkeit, weshalb der Ausschlussgrund von <ref-law> nicht gegeben ist. Die Streitwertgrenze von Fr. 15'000.-- (Art. 51 Abs. 1 lit. a, Art. 85 Abs. 1 lit. b BGG) ist überschritten.
1.2 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten können Rechtsverletzungen im Sinne von <ref-law> gerügt werden. Rügen gegen die Sachverhaltsfeststellung sind nur zulässig, wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann. "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2 S. 252). Die Rüge, im Rahmen der Sachverhaltsfeststellung sei der grundrechtliche Anspruch auf rechtliches Gehör verletzt worden, kann jedoch uneingeschränkt erhoben werden (Urteil des Bundesgerichts 1C_ 204/2007 vom 24. Januar 2008 E. 1.2.1).
2. 2.1 Der Beschwerdeführer macht geltend, die Kündigung sei vor Gewährung der Einsicht in die Akten der kündigenden Baudirektion erfolgt, womit die Baudirektion § 10 Abs. 3 Personalgesetz verletzt habe. Diese Verfahrensnorm schreibe das rechtliche Gehör zeitlich zwingend vor Erlass der Kündigung vor. Die Verletzung einer Verfahrensnorm bewirke die Missbräuchlichkeit der Kündigung genauso, wie wenn eine Kündigung sich nicht auf sachliche Gründe stützen würde (§ 13 Personalgesetz). Folge der Missbräuchlichkeit sei eine Entschädigung (§ 14 Personalgesetz). Der Beschwerdeführer habe die Akten je mit Eingaben vom 4. März 2006 und vom 13. April 2006 verlangt. Spediert worden seien die Akten tatsächlich erst am 31. Mai 2006, während die Kündigung am 16. Mai 2006 erfolgt sei. Weder im Schreiben vom 1. März 2006 noch in jenem vom 16. März 2006 habe die Baudirektion Zusammensetzung und Inhalt der sich bei ihr befindlichen Verfahrensakten bekannt gegeben. Die vorinstanzliche Schlussfolgerung, das rechtliche Gehör des Beschwerdeführers bzw. dessen Recht auf Akteneinsicht sei gewahrt gewesen und Verfahrensrechte somit nicht verletzt worden, indem die Kündigung nur auf den dem Beschwerdeführer aus dem FFE-Verfahren bekannten Akten abgestellt habe, erweise sich vor den Grundsätzen des rechtlichen Gehörs als offensichtlich unhaltbar.
2.2 Der Umfang des Anspruchs auf rechtliches Gehör wird zunächst durch die kantonalen Verfahrensvorschriften umschrieben. Unabhängig davon greifen die aus <ref-law> folgenden Verfahrensregeln zur Sicherung des rechtlichen Gehörs Platz (<ref-ruling> E. 2.1.1 S. 161). Gemäss § 10 Abs. 3 Personalgesetz ist dem Mitarbeiter vor der Kündigung das rechtliche Gehör zu gewähren. Nach § 16 Abs. 1 des Gesetzes des Kantons Zug vom 1. April 1976 über den Rechtsschutz in Verwaltungssachen (Verwaltungsrechtspflegegesetz; BGS 162.1) haben die Parteien Anspruch auf Einsicht in die Akten, soweit nicht überwiegende öffentliche oder private Interessen entgegenstehen. Dass sich aus dem kantonalen Recht ein weitergehender Gehörsanspruch als aus <ref-law> ergeben würde, wird nicht behauptet und ist auch nicht ersichtlich.
Das rechtliche Gehör dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheides dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass des Entscheides zur Sache zu äussern, Einsicht in die Akten zu nehmen und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (<ref-ruling> E. 3.2 S. 494; <ref-ruling> E. 2.2 S. 504 f., je mit Hinweisen).
Aus Inhalt und Funktion des Akteneinsichtsrechts als Teil des Anspruchs auf rechtliches Gehör folgt nach der Rechtsprechung, dass den Beteiligten grundsätzlich sämtliche beweiserheblichen Akten gezeigt werden müssen, sofern in dem sie unmittelbar betreffenden Entscheid darauf abgestellt wird. Es gehört zum Kerngehalt des rechtlichen Gehörs, dass der Verfügungsadressat vor Erlass eines für ihn nachteiligen Verwaltungsaktes zum Beweisergebnis Stellung nehmen kann. Das Akteneinsichtsrecht ist somit eng mit dem Äusserungsrecht verbunden, gleichsam dessen Vorbedingung. Der Rechtssuchende kann sich nur dann wirksam zur Sache äussern und geeignete Beweise führen oder bezeichnen, wenn ihm die Möglichkeit eingeräumt wird, die Unterlagen einzusehen, auf welche sich die Behörde bei ihrer Verfügung gestützt hat (<ref-ruling> E. 3.1 S. 388 f. mit Hinweisen).
Das Akteneinsichtsrecht bezieht sich auf sämtliche verfahrensbezogenen Akten, die geeignet sind, Grundlage des Entscheids zu bilden. Die Akteneinsicht ist demnach auch zu gewähren, wenn die Ausübung des Akteneinsichtsrechts den Entscheid in der Sache nicht zu beeinflussen vermag. Die Einsicht in die Akten, die für ein bestimmtes Verfahren erstellt oder beigezogen wurden, kann demnach nicht mit der Begründung verweigert werden, die fraglichen Akten seien für den Verfahrensausgang belanglos. Es muss vielmehr dem Betroffenen selber überlassen sein, die Relevanz der Akten zu beurteilen (<ref-ruling> E. 3.2 S. 389, mit Hinweisen).
Bei der Akteneinsicht ist zwischen der gegenwärtigen Prüfung, d.h. ob dem fraglichen Akt im aktuellen Verfahren Beweischarakter zuzuschreiben ist oder nicht, und der nachträglichen Prüfung, - etwa im Beschwerdeverfahren -, d.h. ob die Behörde durch Nichtvorlegung des fraglichen Aktenstücks eine Gehörsverweigerung begangen hat, zu unterscheiden. Steht eine nachträgliche Prüfung zur Diskussion und stellt die Behörde fest, dass der fragliche Akt im vorinstanzlichen Verfahren objektiv nicht als Entscheidgrundlage in Frage kam, kann eine Gehörsverletzung verneint werden (Michele Albertini, Der verfassungsmässige Anspruch auf rechtliches Gehör im Verwaltungsverfahren des modernen Staates, 2000, S. 228).
Einblick zu gewähren ist prinzipiell auch in Aktenstücke, deren Inhalt dem Gesuchsteller bekannt ist. Die Behörde kann grundsätzlich nicht ein beweiserhebliches Aktenstück von der Einsicht mit der Begründung ausnehmen, dass dessen Inhalt dem Betroffenen bekannt ist. Bestehen keine konkreten, objektiven Anhaltspunkte, dass der Betroffene über den konkreten Inhalt des Aktenstückes im Bild ist, so ist ihm das Dokument grundsätzlich zur Einsicht vorzulegen (Urteil des Bundesgerichts vom 23. Februar 1977 E. 2b/aa, in: ZBl 78/1977 S. 376). Verfügt hingegen der Betroffene über ein Exemplar desselben, erweist sich eine Einsichtsgewährung im fraglichen Akt an sich generell als unnötig (Albertini, a.a.O., S. 228).
2.3 Im vorliegenden Fall steht ausser Frage, dass das Hochbauamt des Kantons Zug dem Beschwerdeführer das Aktendossier erst zwei Wochen nach dem Erlass der Kündigungsverfügung vom 16. Mai 2006 zustellte. Das Verwaltungsgericht erwog, dass der Beschwerdeführer im Zeitpunkt des rechtlichen Gehörs von allen beweiserheblichen Akten Kenntnis hatte und sich dazu ausführlich äussern konnte und dies auch getan habe, bevor die Baudirektion die Kündigung des Arbeitsverhältnisses verfügt hatte. Damit sei das Akteneinsichtsrecht und somit auch das rechtliche Gehör nicht verletzt.
2.4 Die Auflösung des Arbeitsverhältnisses erfolgte vorliegend mit der Begründung, aufgrund der bekannten und aktenkundigen Vorfälle (bedauerliche private Probleme, welche zu einem vollkommen negativen Bild von Justiz und Verwaltung geführt hätten; Äusserungen, in denen ein gewisses Verständnis für den Attentäter A._ gezeigt wurde; offene und unterschwellige Drohungen, die dem Arbeitsverhältnis die Vertrauensgrundlage entzogen hätten) sei eine weitere Zusammenarbeit nicht mehr möglich. Rechtsrelevant sind deshalb diejenigen Aktenstücke, welche sich auf die genannten Kündigungsgründe beziehen.
Unter den erst nach der Kündigung dem Beschwerdeführer zur Einsicht vorgelegten Akten befindet sich unter anderem das Personaldossier des Beschwerdeführers, welches alle Unterlagen in bezug auf die Begründung seines Arbeitsverhältnisses, seine Arbeitsleistungen, seine Absenzen, seine Zeugnisse und ähnliches enthält. Da indessen die Kündigung nicht mit schlechten Arbeitsleistungen des Beschwerdeführers begründet wurde, sind diese Aktenstücke für das vorliegende Verfahren entgegen der vom Beschwerdeführer vertretenen Auffassung nicht relevant. Hinzu kommt, dass der Beschwerdeführer teilweise schon zu einem früheren Zeitpunkt Einsicht in diese Akten genommen hatte.
Massgebend sind vielmehr diejenigen Akten, auf welche die Baudirektion bei ihrem Entscheid vom 16. Mai 2006 abgestellt hatte. Es handelt sich somit um diejenigen Aktenstücke, welche sich auf den Vorfall vom 30. September 2005, der zur Einweisung des Beschwerdeführers in die psychiatrische Klinik führte, beziehen.
Nach der für das Bundesgericht verbindlichen Sachverhaltsdarstellung der Vorinstanz wurden nachträglich die Aktennotiz des Kantonsbaumeisters vom 1. Oktober 2005 über die Vorfälle vom 30. September 2005, eine Kopie einer E-mail von B._ an C._ vom 10. Dezember 2003, worin dieser seine Sorge über den Zustand des Beschwerdeführers zum Ausdruck brachte, sowie eine E-mail von B._ an den Kantonsbaumeister vom 3. Oktober 2005, die Fragen zum weiteren Vorgehen aufwarf, zur Einsicht vorgelegt. Wie die Vorinstanz zu Recht erwog, sind die beiden letzteren Aktenstücke für das vorliegende Verfahren nicht von Relevanz. Hingegen kam der Aktennotiz des Kantonsbaumeisters vom 1. Oktober 2005 bei der Kündigung entscheidende Bedeutung zu. Der Beschwerdeführer stellt nicht in Abrede, dass ihm dieses Aktenstück aus dem FFE-Verfahren vor dem Bezirksgericht Zürich und vor dem Untersuchungsrichteramt Zug bekannt war. Er wies denn auch in seiner Stellungnahme zu den Kündigungsgründen vom 13. April 2006 an die Baudirektion darauf hin, dass ihm "die vertrauliche Aktennotiz des Kantonsbaumeisters" vorliege. Unter diesen Umständen erscheint es aber nicht verfassungswidrig, wenn die Baudirektion auf die Herausgabe der fraglichen Aktennotiz des Kantonsbaumeisters vom 1. Oktober 2005 im damaligen Zeitpunkt verzichtete. Der Beschwerdeführer war über den konkreten Inhalt des fraglichen Dokuments im Bild und konnte demzufolge seine Sicht der Dinge in das Kündigungsverfahren einbringen. Aufgrund der beiden Schreiben der Baudirektion, die ihm die einzelnen Kündigungsgründe detailliert aufzeigten, musste ihm auch klar sein, dass die Umstände im Zusammenhang mit dem Vorfall vom 30. September 2005, welche in der fraglichen Aktennotiz beschrieben waren, für die geplante Auflösung des Arbeitsverhältnisses von entscheidender Bedeutung waren. Es wurde dem Beschwerdeführer auch Gelegenheit eingeräumt, zu den gegen ihn erhobenen Vorwürfen Stellung zu nehmen, was er mit Eingaben vom 4. März 2006, 13. April 2006 und 29. April 2006 auch tat. Eine Verletzung des Akteneinsichtsrechts und damit des rechtlichen Gehörs im Sinne von § 10 Abs. 3 Personalgesetz liegt somit nicht vor. Hinzu kommt, dass bereits am 20. Januar 2006 im Rahmen eines Gesprächs zwischen dem Vertreter des Beschwerdeführers und der Leiterin des Personalamts sowie dem Kantonsbaumeister eine allfällige Beendigung des Arbeitsverhältnisses in Betracht gezogen worden war. Im öffentlichen Dienstrecht können auch relativ informelle Äusserungsgelegenheiten vor der Kündigung dem verfassungsrechtlichen Gehörsanspruch genügen, sofern dem Betroffenen klar war, dass er mit einer solchen Massnahme zu rechnen hatte (Urteile des Bundesgerichts 1C_103/2007 vom 7. Dezember 2007 E. 5.3; 2P.275/2005 vom 1. März 2006 E. 2.1).
2.5 Nach dem Gesagten fällt eine Verletzung des rechtlichen Gehörs resp. des Rechts auf Akteneinsicht ausser Betracht. Der in diesem Zusammenhang gleichzeitig erhobenen Willkürrüge kommt keine eigenständige Bedeutung zu; sie fällt mit der Rüge der Verletzung des rechtlichen Gehörs zusammen und ist daher unter diesem Aspekt nicht mehr zu prüfen.
3. Ausgangsgemäss wird der Beschwerdeführer kostenpflichtig (<ref-law>). Die Zusprechung einer Parteientschädigung im Verfahren vor Bundesgericht fällt ausser Betracht (<ref-law>; Urteil 1C_68/2007 vom 14. September 2007 E. 5).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zug, Verwaltungsrechtliche Kammer, schriftlich mitgeteilt.
Lausanne, 6. April 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Schoder