Deterministic variants of (EC)DSA described in [1] are good candidates for signing. No per-signature-randomness is required with these, which is the major drawback with the plain (EC)DSA. The signatures as short (compared to RSA) and backward compatible.

Curve 25519, specifically Ed25519 from [2], can also be used for signatures, not only public key encryption. There's not as much cryptanalysis available as with the DSA family, however.

Regarding the HMAC, I'd stay with the choice made by the NaCl library authors, that is HMAC-SHA-512-256 (see [3]).

Even if not mentioned, a high quality key derivation function might come handy. scrypt ([4]) seems as a nice candidate if one feels adventurous.

1. http://tools.ietf.org/html/draft-pornin-deterministic-dsa-00 (RFC draft)
2. http://ed25519.cr.yp.to/
3. http://nacl.cr.yp.to/auth.html
4. http://tools.ietf.org/html/draft-josefsson-scrypt-kdf-01 (RFC draft)

Signing: I personally would stick to RSA-alikes, since I have not understood EC yet. I guess that RSA is better analyzed than Rabin-Williams, so my choice would be RSA. (But I did not analyze the provided suggestions deeply, so perhaps someone has better arguments) Regarding RSA, make sure you get your padding right!
Public key Encryption: Again, I personally dislike EC.
Message Digest: Unless you have strict space/time constraints, I would suggest KECCAK|SHA1|MD5 (all 3 appended together, to avoid cryptoanalytical breakthroughs in either of them)
Secret Key Encryption: AES-128 or AES-256, yes, I agree there.

Signing: RSA for security & maturity, ECC for efficiency.
Hash: KECCAK or SHA-2 (for hardware acceleration).
Encryption: AES-128/256 (for hardware acceleration).

I'd suggest we focus on doing high assurance base implementations of what good algorithms and protocols we already have. Implementations are flawed more often than the algorithms themselves. Cryptol and SPARK are both proven in this regard.