Logic should be taught from the intuitive aspects first before turning it formal; With lots of domain examples to show how sentences often have a common Form (i.e. structure) which can then be generalized as Symbolic Logic ranging over a Domain of Discourse/Domain of Interpretation. Once this distinction between "Structure/Form"(i.e. Syntax) and "Meanings"(i.e. Semantics) is grasped then mechanical manipulation strictly following rules, starts to make sense.

Instead, what is taught is starting with truth tables for logical operators and thus students simply don't learn to think/understand. For example, almost everybody is thrown off by the "implication" logical operator (evaluates to True when the antecedent is False irrespective of the consequent). But if you use some actual domain examples then it becomes clear why it is so.

Alfred Tarski's classic book mentioned above does a good job of building up logic from the first principles and hence is a great companion to any standard textbook.