As important as the Fibonacci sequence and it's its related sequences are in the overall hierarchy of functions, it just doesn't come naturally to most beginners and the depth of it's its many interconnections with diverse areas of mathematics will be lost on most of them. Your examples are clever, but I seriously doubt unless your audience is made up of very strong undergraduates with math competition experience and therefore quite bit of familiarity with counting problems, your examples are likely to be met with chirping crickets being heard clearly......clearly...
Geometry and physics are much more familiar to a general mathematical audience and linear algebra has so many connections with these topics, it’s really much more natural to start with those. These are my favorite examples to give. Describe planes in R3 as linear subspaces of R3, add vectors displaying their parallel lines, give isometries as examples of linear transformations and then construct matrices for them with respect to several possible bases. Show the fundamental theorem of systems of linear equations geometrically (i.e. that the corresponding systems of lines can be parallel, perpendicular or coincident). And then discuss similarities and their corresponding row vectors as eigenvectors of the corresponding eigenspaces. And then you can solve systems of differential equations as your last magic trick.
To prepare for the lecture, I'd look at Linear Algebra Through Geometry by Thomas Banchoff and John Wermer as well as the classic Linear Algebra With Applications by Gilbert Strang. Lots of good ideas and examples in these books to guide you in preparing this talk.
If you want a lot of very nice specific examples to use in your talk, there’s a terrific discussion and application of convergent sequences of diagonalizable stochastic matrices to solve problems such as the likelihood of graduation of students at a community college and the proportion at any given time of city and rural dwellers in a populated area undergoing mass migrations in the 4th edition of Steven H. Friedberg, Arnold J. Insel and Lawrence E. Spence’s Linear Algebra. It’s in section 5.3.
