Random matrix theory (RMT) and the theory of orthogonal polynomials (OPs) have long been connected, as some of the seminal results in RMT used OPs in a fundamental way. OP methods typically enter numerical linear algebra (NLA) through the analysis of Krylov subspace methods. To close the loop, NLA has also been connected with RMT for years, going back to the seminal work of Goldstine and von Neumann. This talk will further explore the connections between these three topics, by examining algorithms on large random matrices. The results of this study motivate new analyses of old algorithms and the development of new methods.