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 like the idea of using a general case to keep things simple. Easier to read and less room for error. That's worth the extra bytes.
But maybe we can optimize it just one bit (save 3 opcodes) since we know n is at least 2.
General case for m-of-n:
ScritpSig: sig1 pubkey1 sig2 pubkey2 ... sigN pubkeyN
....any sig/pubkey pair may be a placeholder (e.g. OP_0 OP_0)
ScriptPubKey:
TUCK CHECKSIG SWAP HASH160 {pkhash} EQUAL BOOLAND
OVER 2SWAP CHECKSIG SWAP HASH160 {pkhash} EQUAL BOOLAND ADD // n-1 times
m GREATERTHANOREQUAL
(1 and 2) or 3:
ScritpSig: sig1 pubkey1 sig2 pubkey2 sig3 pubkey3
....any sig/pubkey pair may be a placeholder (e.g. OP_0 OP_0)
ScriptPubKey:
TUCK CHECKSIG SWAP HASH160 {pk3hash} EQUAL BOOLAND DUP ADD // If sig3/pubkey3 checks out, then this evaluates to 2
OVER 2SWAP CHECKSIG SWAP HASH160 {pk2hash} EQUAL BOOLAND ADD
OVER 2SWAP CHECKSIG SWAP HASH160 {pk1hash} EQUAL BOOLAND ADD
2 GREATERTHANOREQUAL