Στα τέλη της δεκαετίας του 1980 η πολιτική δραστηριότητα του Ανδρέα Λεντάκη εισέρχεται σε νέα φάση. Mέλος της Εκτελεστικής Επιτροπής του Συνασπισμού, αναδείχθηκε βουλευτής του το 1989 και το 1990. Τον Ιούλιο του 1993 παραιτήθηκε ταυτόχρονα από πρόεδρος της ΕΔΑ και από βουλευτής και προσχώρησε στο νεοσύστατο κόμμα της ΠΟΛ.ΑΝ συντασσόμενος με τον Αντώνη Σαμαρά για το Μακεδονικό ζήτημα. Εξελέγη βουλευτής στην Β’ Αθήνας (πρώτος σε σταυρούς) τον Οκτώβριο του 1993 και ορίστηκε κοινοβουλευτικός της εκπρόσωπος. Ήταν η αριστερή φωνή ενός πολυσυλλεκτικού κόμματος. Αναδείχθηκε σε πρώτο ομιλητή της Βουλής κατά την περίοδο 1993-1994. O απολογισμός του έργου του (1993-1996) ήταν εντυπωσιακά μεγάλος: 597 ερωτήσεις σε υπουργούς, 73 επίκαιρες ερωτήσεις, 285 αναφορές.
Διετέλεσε μέλος της Διακομματικής Επιτροπής του Κοινοβουλίου στη Βορειοατλαντική Συμμαχία, της Διακομματικής Επιτροπής στο Συμβούλιο της Ευρώπης, της Διακομματικής Επιτροπής στην Ευρωπαϊκή Ένωση, της Επιτροπής Παιδείας και Πολιτισμού και της Επιτροπής Θρησκευμάτων και Ορθοδοξίας, της οποίας διετέλεσε και Γραμματέας.
Εντυπωσιακές για τη δομή του λόγου του και την τεκμηρίωσή τους χαρακτηρίζονται οι αγορεύσεις του στο Ελληνικό Κοινοβούλιο. Συνέβαλε σε σημαντικό βαθμό στη θεσμοθέτηση του δεύτερου βαθμού Αυτοδιοίκησης της Νομαρχιακής.
Οι Καθηγούμενοι Ιερών Μονών Μετεώρων του απέστειλαν ευχαριστίες για την καθοριστική του παρέμβαση, ενώ χαρακτηρίζουν μνημειώδη το λόγο του για τη διατήρηση της ιερότητας του περιβάλλοντα χώρου των Αγίων Μετεώρων, με αποτέλεσμα να μην επιτρέπεται η εμπορική του εκμετάλλευση.
O Σύλλογος Ελλήνων Αρχαιολόγων αναγνωρίζει τη σημαντικότατη συνεισφορά του στην διάσωση της ιστορικής μας κληρονομιάς με τις πολύ καθοριστικές παρεμβάσεις του στις απειλούμενες καταστροφές μνημείων και χώρων με τελευταία την καταλυτική του παρέμβαση για την παρέκκλιση του ΜΕΤΡO στον Κεραμεικό και την σωτηρία των μνημείων.
Το 1989 προτείνει με βαθιά δημοκρατική συνείδηση, μοναδική τόλμη και μεγαλείο ψυχής την αποφυλάκιση των απριλιανών για λόγους ανθρωπιστικούς και πολιτικούς, που τεκμηριώνει και ιστορικά και την ίδια πρόταση επαναλαμβάνει στην Βουλή το 1996.
Τον Οκτώβριο του 1994 κατέρχεται ως υποψήφιος δήμαρχος Αθηναίων με συνυποψήφιους τον Θ. Πάγκαλο, τον Δ. Αβραμόπουλο, την M. Δαμανάκη και τον Λ. Aυδή, με ποσοστό 4,3%. Οι προτάσεις του μέσω του Συνδυασμού του “Δικαίωμα στη Ζωή” είναι ρηξικέλευθες και πολλές τοποθετούνται στα προγράμματα αργότερα άλλων πολιτικών, όπως αυτές για την δημιουργία Μητροπολιτικών Κέντρων Αθήνας και Θεσσαλονίκης.
Έντονη δραστηριότητα παράλληλα επέδειξε σε επίπεδο συγγραφικού έργου, αλλά και διαλέξεων σε πανεπιστήμια, ομιλιών – εισηγήσεων – παρεμβάσεων σε επιστημονικά συνέδρια, συμπόσια, ημερίδες, με αντικείμενο την πολιτική, την ιστορία, την φιλολογία και την κοινωνική ανθρωπολογία.