"I don't want to download anything to my PC, it could have a virus". Surprisingly this is the number one objection we get from new users.

So in the altcoin I founded (in sig if interested), we have created a simple two step process to get them started:

1. Sign up for the online wallet (less scary for them)
2. Go to our faucet for some coins to get started.

Once they do that, they are curious, so on our forum they can find places to spend their coins, and can later download the full wallet to mine, etc.

I think that strategy is what we need to do with bitcoin as well.
You can read more on what is like building a user community on my post: bitcointalk.org - Re: How we crypto-geeks get it wrong & the reality of altcoin success