There may be a way to compile C# code to include the .NET libraries compiled right into the executable, but I'm sure it's not really supported by Microsoft.
I googled C# native compiler and found a link to this...
http://www.remotesoft.com/
Maybe try others? I have no idea how well this works so you'll have to do the digging on your own.
For what it's worth, most computers running Windows have .NET on them now. It's kind of an expected install. I think Windows 7 even puts it on as a part of windows update, but I'm not 100% sure on it so don't quote me.
If this is a huge issue, I'd honestly consider doing your programs in ANSI C++. C# is kinda like Java... it's just expected that you have the required frameworks/libraries installed.