To the extent that this question is on topic here (that is, without reference to literature on mathematical education), I would propose that experimenting with concrete instances is not antithetical to the development of abstract concepts.
In an educational setting in computer science, it should be clearly stated and agreed upon that formal reasoning is the goal, and aquiring an intuitive grasp on things is not enough. After this is established (not trivial, literally counterintuitive), abstractions and concrete examples can help each other, not get in the way of each other.
The thing is, formal reasoning is not something that we do, it is what we are as a field - which is why studying the history of computing is so important. It can be tedious though, unnerving sometimes. It must be gradually developed as a habit. Intuitions are naturally captivating, and that is why we tend to rely on them to motivate our students, but there is something captivating about formalization too. Our challenge is to bring it to the center of the stage.