I think the best thing for a beginner is to focus on concrete interesting mathematics. You definitely do not want to do any abstract stuff at this point unless it is motivated by some concrete problem. I recommend "Nets, Puzzles and Postmen" by Peter Higgins, and later on "How to Prove It" by Daniel Velleman. The first book is a really unique book, in that it is written at the layman level but does not handwave any of the core mathematical ideas, and furthermore it has notes for advanced readers!
I want to also note that playing combinatorial games (e.g. Hex, Go, ...) can be very helpful for honing intuition of quantifiers, because if you think about it a winning strategy of maximal length $k$ is nothing but a true sentence with $k$ alternating quantifiers. There are also many nice puzzles with very strong mathematical flavour such as Tatham's puzzles and Manufactoria. These can very easily inspire an investigation into reductions (i.e. if I can solve one puzzle easily I can solve another one too) and also encourage thinking about NP-hardness (i.e. it is possible that it is easy to verify a solution but hard to find one), which in some sense is similar to hardness of mathematical proofs (i.e. it is easy to verify a formal proof but may be hard to find one or even know whether one exists).
If your brother loves mechanical puzzles such as the Rubik's cube, you can happily explore various invariants with him as well. One very important invariant, namely parity of the pieces in each group (sides and corners), is crucial to a complete understanding of solving it and many other permutation puzzles.
It may also be of interest to you that my interest in mathematics grew out of playing around with such concrete mathematics, and one example I clearly remember from my childhood was investigating the relation between the forward difference iterates and the original sequence. Although at that time I did not know any of the terms, I knew about Pascal's triangle, which was enough to find and understand the decomposition of any given polynomial sequence into a weighted sum of (diagonal) columns of Pascal's triangle, where the weights can be easily obtained from the forward difference iterates. You can take a look at this post for a high-level explanation that I wrote up many many years later, but certainly the way to teach such stuff to your brother is via Pascal's triangle and not the abstract operator viewpoint. Well, at least not so soon. =)