I face a dillemma here. How do I get the bitcoin client into a non internet connected machine? This is assuming that you can never 100% trust the computer you're using to download the client. Along each step in the process of securing your bitcoins there is a small but every so slightly possible risk. Heck the client itself could be compromised. A hacker could break into the sourceforge servers and cleverly attach a payload into the official client. Guess how many people would not notice until it was too late.

I think the safest and most paranoid idea I've head so far is to physically print your private keys. I am even tempted to print them on a freaking gold plate!