How can I deploy a C# application if users don't have .NET installed?

Anyone who wants to run your program needs the appropriate version of the .NET Framework installed. There's no way to work around this. It honestly amazes me how often this question gets asked. You can't compile .NET code down to any kind of a "native binary", and you can't distribute only the portions of the framework that you need. If all of this was important to you, you should have chosen a different development platform in the beginning.

Your only option is to bundle the .NET Framework along with your application's installer. The way to make this easiest on your customers is to use Visual Studio to create a setup project that will automatically install the .NET FW if they don't have it already, and then install your application, all in a single step process.

Visual Studio has built-in support for creating such a setup project, and most of the dirty work is handled for you. File -> New Project -> Other Project Types -> Setup & Deployment -> Visual Studio Installer. Then, pick either the "Setup Project" or "Setup Wizard" option, and follow the instructions.

The only thing to keep in mind since you've developed for .NET 4.0 is that there are two versions of this framework: the full version and the "Client Profile". The Client Profile is an attempt to do exactly as you mention and install only the portions of the framework that are used by the typical application. You have to first figure out of this is a deployment option for you. If your program uses classes that are not available in the Client Profile, you need to install the full version. Otherwise, you can consider installing the Client Profile, which is the default for all new projects targeting .NET 4.0 in VS 2010. Check the "Target Framework" settings for your application, under the project Properties. If it's not set to Client Profile already, try changing it and see if it will compile. That's the quickest way to tell if this deployment option is available to you. But there's only about a 15% difference in size between the two frameworks, so it isn't really that big of a deal if you must deploy the full version.

Either way, the setup project will automatically determine and bundle the correct version for your app. Definitely don't make the user download and run the .NET installer separately. Use the setup project and do this for them automatically. If you don't have VS or don't want to use the one it provides, investigate alternatives, like Inno Setup, which also support deploying and installing the .NET runtime with an app.

In many cases you do not need the entire .NET Framework 4.0 and can use the much smaller .NET Framework Client Profile. You can then use an installer to bundle the client profile installer with your app into a single deployment.

You cannot run a .NET app without the framework. If this is a deployment issue for your customers, you should consider either a Click-Once installer (web-based automated installation and updating) or porting the app to Silverlight.