When this is merged and widely used, what new types of transactions become possible?
It's not exactly "15 operations"...
The Bitcoin address is not really a public key, but a special script that is built from special commands. From those commands you could build really weird transactions, for example the ones mentioned here, that lock funds on an address that can be accessed only if someone manages to break SHA2.
Up until now the miners treated anything besides the basic four or so script kinds as non-standard. It meant that you could add them to the blockchain (because they are valid), but only if you mine them yourself, or convince one of the pools to add them to the block.
Thanks to the relaxed rules, you will be able to create transactions that are redeemable by almost any script built from commands listed here: https://en.bitcoin.it/wiki/Script . As long as they don't contain more than 15 signature checks.
The biggest potential use case for this is probably in oracles / smart contracts, as explained in Gavin's bit-thereum post. Our project - Orisi / Distributed Oracles is right now the only practical implementation of this concept, and it's described in detail in our white paper ( https://github.com/orisi/wiki/wiki/Orisi-White-Paper ). We may be using the extended scripts to perform a 1+M of N multisig check - that is to require a signature of both the transaction sender, and M of N oracles protecting the transaciton. If this explaination is not clear enough, you might want to check our website.
Finally, as for this functionality's ETA - it might appear in the next minor update, but that will happen probably in a few months time.