What we need is a construction that is as secure as the strongest underlying primitive. For instance, for symmetric encryption: Let M be the secret message, C1 the first cypher, C2 the second cypher, K1 and K2 two randomly generated, independent keys. Oh, and a nonce, but let's ignore that for now.

I Think it is easy to prove that C1(K1, C2(K2, M)) is at least as hard to break as either C1(K1, M) or C2(K2, M). Because if one of the cypher is easy to crack, the other can still work.

Hashes are different, because they're not reversible. In this case, a bad hash could indeed project the input space into a smaller output space than expected, and previous or subsequent hashes cannot reverse this mistake.

Hashes: What about xor'ing together hashes from two or more algos? Even if one just hashed to all-1, it wouldn't matter.

Only if the hash algorithms aren't correlated, they should ideally be of different designs.

Dunno. Looks promising.