This study proposes and examines the generalized John polynomials (also referred to as generalized Leonardo-Pell polynomials), a novel sequence developed by merging the attributes of Leonardo and Pell numbers within a second-order linear non-homogeneous recurrence framework. To analyze their foundational characteristics, five specific sub-cases of this polynomial family are isolated and examined in detail, including the MinMax polynomials defined by Horadam and the new John-Lucas polynomials formulated in this study. The primary algebraic contributions of this work include establishing the general solutions, Binet-type formulas, and both ordinary and exponential generating functions for this new polynomial sequence. The findings ultimately reveal that these polynomials also conform to a third-order homogeneous recurrence relation. Through analytical approaches, exact combinatorial representations for the new polynomial family are derived by applying partial fraction decompositions alongside power series. Furthermore, classical identities well-documented in the literature specifically the formulas of Catalan, d'Ocagne, Vajda, and Honsberger are successfully adapted and proven within the context of this broader non-homogeneous structure. In terms of linear algebra and matrix theory applications, determinantal representations are achieved by utilizing the Doolittle algorithm for LU decomposition. Additionally, the construction of third-order square matrix representations enables the extraction of structural relationships, such as Simpson's identity. Finally, matrix differential calculus techniques are utilized to formulate explicit derivative identities for the generalized John polynomials.