It sounds like you're losing steps on the retract stroke. The machine thinks it's gone farther up than it really has, so it sends the bit deeper from its false starting point. That would account for the "struggling" you noted, since it's trying to cut more wood than was called for.
Yes, you do need to tighten the collet with wrenches - hand-tight won't work. Yes, a two-flute bit is much better for cutting wood and other soft materials than a 4-flute, which is generally only used for steel.
It doesn't sound like feeds and speeds are really the problem, since slowing down didn't help. Try reducing the acceleration on the Z axis by half, if that's the one that's losing steps. If other axes are also faulting, reduce the accelleration on them as well. See if that helps (using a spoil board this time), The other way to avoid losing steps on the upstroke is to fit the machine with a counterweight or gas strut to help offset the weight of the spindle (or whatever you're using instead of one). .