A C# app will need an implementation of the CLR (.NET) running on the local machine in order to run. A Java app will need an implementation of the JVM so it is really no different. On Windows, I would expect most people to have a .NET install.
Take a look at the Mono project as far as running it on Linux and Mac:
http://mono-project.com/Main_Page
One thing you can consider is using an older version of the .NET framework to ensure that the greatest number of people have it installed. I would use .NET 3.5 or even 2.0 if you do not need fancy new features. That would have been installed already on Windows 7 for example.
Since the Windows 7 user had to download the framework I assume you are currently targeting .NET 4 which means you must be using Visual Studio 2010 (or an express version). Here is a link that tells you how to target a different version of the framework:
http://msdn.microsoft.com/en-us/library/bb398202.aspx
One quick note about Mono, it is an excellent cross-platform option but it does not support the Windows Presentation Foundation (WPF) GUI framework at this point. You will either have to use Windows Forms or create different front-ends for different platforms.
If you want to create a Linux GUI (also available on Windows and Mac) you can try GTK#:
http://www.mono-project.com/GtkSharp
For a Mac native GUI you can check out MonoMac:
http://mjhutchinson.com/journal/2010/06/09/monomac_in_monodevelop
An excellent IDE for cross-platform .NET development is MonoDevelop (it will read your VC# project files):
http://monodevelop.com/