I like BlockChain. There's still an amount of trust and I can think of ways it could be compromised, but they do a pretty good job architecturally of preventing your loss in the case they're compromised (well, depends on how they're compromised)

Anyway, those instructions will give you a secure paper wallet and an account that will enable you to still check your balance through blockchain.info.

(Note, this method keeps your private keys on the paper wallet, and the public key with Blockchain which enables balance checking but prevents compromise via blockchain.info)