We analyze collider signatures of massive color-octet bosons whose couplings to quarks are suppressed. Gauge invariance forces the octets to couple at tree level only in pairs to gluons, with a strength set by the QCD gauge coupling. For a spin-1 octet, the cross section for pair production at hadron colliders is larger than that for a quark of equal mass. The octet decays into two jets, leading to a 4-jet signature with two pairs of jets forming resonances of the same mass. For a spin-0 octet the cross section is smaller, and the dominant decay is into bbar{b}, or tbar{t} if kinematically allowed. We estimate that discovery of spin-1 octets is possible for masses up to 330 GeV at the Tevatron, and 1 TeV at the LHC with 1 fb^{-1}, while the reach is somewhat lower for spin-0 octets.