After much fruitful discussion and evolution, this proposal is now a series of "Bitcoin Improvement Proposals" -- see BIP 11, 12 and 13: https://en.bitcoin.it/wiki/Bitcoin_Improvement_Proposals
Sincere thanks to everybody who contributed improvements, ideas and code.
I still like the previous more generalized solution. Here's a change to make it only do checksig when needed:
ScritpSig: sig1 sig2 sig3
....any unused sig should be OP_0 to avoid unnecessary CHECKSIGs
ScriptPubKey:
0
SWAP DUP NOTIF DROP ELSE pubkey CHECKSIG ADD ENDIF // n times
m GREATERTHANOREQUAL
Basically if the sig is 0, we just drop it. Otherwise, we do the checksig and add 1 to the total if sig checks out.
To save an extra opcode, we could do this: (but it's a bit more complicated)
0
SWAP DUP 0NOTEQUAL NOTIF pubkey CHECKSIG ENDIF ADD // n times
m GREATERTHANOREQUAL
And this is the case if the sender only has the pubkey hashes and the redeemer needs to provide the pubkeys:
ScritpSig: sig1 pubkey1 sig2 pubkey2 sig3 pubkey3
....any unused sig/pubkey pair should be "OP_0 OP_0" to avoid unnecessary CHECKSIGs and HASH160s
ScriptPubKey:
0
OVER 2SWAP NOTIF DROP ELSE OVER CHECKSIG SWAP HASH160 pubkeyhash EQUAL BOOLAND ENDIF ADD // n times
m GREATERTHANOREQUAL