What are good combinations of public key algorithms or primitives for long term security?
For the signatures, hash-based signatures provide a nice solution to your problem: You can use so called hash combiners to instantiate the signature. These are functions that construct a hash function given two or more hash functions and preserve certain properties as long as at least one of the hash function has this property. For example the concatenation combiner:
$C_{H_1,H_2}^{\|}(M) = (H_1(M)\|H_2(M))$

preserves collision resistance and second preimage resistance. 

If you use hash functions based on different design principles, e.g. SWIFFT as one that has certain security guarantees steaming from the hardness of lattice problems and one classically constructed one like SHA-3, you can achieve good redundancy.

The big advantage is, that you do not have to implement two different schemes but only one: You would have to implement two different hash functions for message compression anyway but in addition you would also have to implement two "fixed length" signature schemes for multiple signatures.