The thing I realized this summer after doing many, many pushups on the three courses I have taken in the last year (BMQ, SQ and BIQ)... is that your arms do not necessarily have to be big to do push-ups, nor are they supposed to be.
Overall fitness is important, because if your arms are doing ALL the work, you aren‘t doing the pushups correctly.
My abs and back muscles were just as sore as my arms after doing pushups constantly. In fact, several times we were just in the push up position, not moving, and that really takes a toll on the abs if they‘re weak.
My advice is to do a circuit of pushups, and sit ups, and push ups and sit ups, even changing the pacing (slowly, and quickly)... but do not overtrain as someone else mentioned.
Do different pushups and do them regularly, giving yourself days off to rest.
I‘ll be the first to admit I‘m hardly a big man, but after a while I was holding my own and keeping up with the pushups.
Oh, here‘s another one the para guys love: try the 5th point of flight procedure. Don‘t know what it is? It‘s a sick and twisted move similar to a certain pilates position, with you on your back, legs straight and together, feet 6 inches off the ground, arms straight and fingers pointed, raised above your head, and your chin in your chest. If you can hold that longer than a couple minutes, you‘ll have no problem on a BMQ.