I really think "formal" methods are not a very good idea for educational purposes. For that matter, programming a computer is a "formal" method. Does it succeed as an educational tool?
What is needed is understanding, intuition, and the ability to deal with abstraction. Formal methods hinder all that. Rather, they promote trial and error, hacking, pattern matching, imitation, focusing on syntax. The list goes on and on.
Any piece of rigorous mathematics will teach people how to reason correctly. The simpler the domain, the better it is. All I learnt about reasoning I learnt in high school when I did Euclidean Geometry seriously. Calculus and linear algebra in the University did the rest.
Another attractive alternative is philosophical logic, where they teach people how to think about statements and understand what is the information content and what is a consequence of what. They do that without drowning the students in symbols.
If you take stock of all the top Computer Scientists, you would be amazed how many of them have formal training in philosophy. We are losing all that now because philosophy students now think of Computer Science as a mundane subject. Getting our students to learn some philosophy could counter that to some extent. Get them to work through Bertrand Russell's History of Western Philosophy. That will do wonders.
If they work in programming language theory, you can also have them read Quine, whom I regard as the "god father" of denotational semantics. (Quine was essentially doing denotational semantics of natural language in Word and Object, which was a huge source of inspiration for Christopher Strachey. But this book is quite hard going.) The edited collection Quintessence is a nice source of Quine's ideas for a beginner.
[Note added: One advantage of philosophy over mathematics is that the students get to see debate, i.e., they get to see the "right" argument and the "wrong" argument and see the experts demolish the wrong ones. In mathematics, one never gets to see a wrong argument, which limits its educational value.]