Why did it take so long to find the Higgs? The $W$ and $Z$ boson took a long time to be discovered because they were so heavy; we couldn't produce them in a particle collider until the 80's. But the Higgs boson isn't that much heavier than the $W$ and $Z$, so we presumably have been producing them for decades. The Higgs also couples to just about everything, so it's not hard to make.
Given the above, why did we have to build the LHC to find the Higgs? Was it just a matter of getting enough statistics, or was there another reason?
 A: Electroweak theory told us where to look for the $W$ and $Z$ gauge bosons. For the Higgs, its mass is a free parameter, hence we didn't know where to look for it. Once you start to look in many places for a particle, you also have to factor in the look-elsewhere effect, which basically means that the more places you look for a particle, the higher the chances you only observe a statistical fluctuation.
LEP
Today we know the Higgs mass is roughly $125$ GeV. The LEP collider at CERN, reached a center of mass energy $\sqrt{s}$ of $209$ GeV. This would have been enough to produce the Higgs. But then, $e^+ e^-$ colliders do not have the highest Higgs production cross section. Your statement:

The Higgs also couples to just about everything, so it's not hard to make.

is not correct. The Higgs couples only very lightly to light particles. So you need to produce heavy particles first in order to have a good chance to also produce a Higgs.
At LEP, the Higgs must have been produced by vector boson fusion, just not enough for us to clearly distinguish it from background:

Associated production is also thinkable, but the cross section is very small, since $m_H + m_Z > \sqrt{s}_{LEP}$:

Even smaller would be $ttH$ production:

Long story short, at LEP, the center of mass energy was simply not high enough, since it's not enough to produce the Higgs only, but you have to produce heavy particles first, that then couple to the Higgs.
Tevatron
What about the Tevatron? Surely the Higgs must have been produced copiously at the Tevatron. Why didn't they see it? The answer is that they did see it. Both CDF and $D^0$ reported an excess. In the combined publication, they even reported an "evidence for the presence of a new particle consistent with the standard model Higgs boson". The combination observed a global significance of $3.1 \sigma$.
But the question remains, why "only" a $3.1 \sigma$ excess, although years of data taking? The answer is two-fold: First, the instantaneous luminosity of the Tevatron was relatively small, at least compared to the LHC. The problem is that while using a proton anti-proton collider helps you in raising the cross sections, the production of anti-protons is notoriously slow and you can't easily reach high instantaneous luminosities.
The second reason, and also the general answer to why finding the Higgs was not so easy, lies in the way the Higgs decays:

This image shows the decay channels of the Higgs boson for a given mass. At $125$ GeV, it mostly decays to a $b\bar{b}$ pair. $b$ quarks hadronize and what you see in the detector are two "jets". A two jets event is not a particularly clean signature. In a hadron collider machine, your background is overwhelming. As far as I know, even today, the observation of the $H \to b\bar{b}$ signal has not reached the $3 \sigma$ level in any LHC experiment.
There are two ways around this: Either look for a Higgs produced with another particle or rely on Higgs decaying to other particles. In a Higgs associated production, the $b\bar{b}$ pair is accompanied by a $W/Z$ boson and the sensitivity is much higher, since the background is much smaller. This is what the experiments at the Tevatron observed.
Higgs decaying to $ZZ$ or to $\gamma\gamma$ are particularly clean channels. But the branching fraction $H \to ZZ$ is $2.67$ %, and $H \to \gamma\gamma$ is even only $0.228$ %, so you need a large dataset to see these decays. Such a dataset was not available in time at the Tevatron.
It is interesting to note, that if the Higgs would have been lighter, it would have been produced copiously at LEP, and we would have found it a long time ago. If it would have been heavier, the branching fraction to $b\bar{b}$ would have been considerably smaller, and we would have observed it at the Tevatron. The mass of $125$ GeV simply turned out to be a signal which was hard to distinguish from background, for various, aforementioned reasons. That's why it took so long to find the Higgs.
