In my personal experience, the hard part for a beginner is not the actual programming, but the environment. Fussing with the command line to compile and link a program, or setting up system environment variables, class paths etc. pp. can be a frustrating experience. I would argue that for a beginner a good IDE is an important tool to getting you up and running, having fun and keeping motivated.

I would therefore recommend something highly integrated like Visual Studio C# Express Edition which you can download for free. If you have Microsoftphobia, the alternative would be Java with Eclipse.

Having said that, at one point you HAVE to leave the "kiddie pool" and jump into the deep end. For that I would second the recommendation of Kernigham & Ritchie's The C Programming Language.

The order of these two steps is up for debate...