I'd say the Tutte Graph, which is a counterexample to
Tait's conjecture: Every 3-connected cubic planar graph has a Hamiltonian cycle.
Initially, I thought this counterexample was extremely non-instructive, since I assumed that Tutte discovered it via some ingenious trial and error. But, after seeing a talk by Bill Cunningham, I discovered how Tutte came up with his counterexample and why it is a counterexample (it's unclear from looking at Tutte's graph that it is not Hamiltonian). The idea is quite simple but useful. Tutte assumed that Tait's conjecture was true and proceeded to prove a sequence of stronger (yet equivalent) conjectures. He then found a very small counterexample to the strongest conjecture, and then deconstructed the sequence of proofs to obtain a counterexample to Tait's conjecture.
I really like this method because it shows that there is hope for a mathematical caveman like me as long as I use my brain. That is, the counterexample was actually not pulled out of thin air like I initially thought.
