I've been very happy with "Visual C# 2008 How to Program (3rd Edition)" by Deitel. It is written as a text so there are some "assignments" at the end of most chapters, which I found really useful. The main thing I like is that covers C# from a programming standpoint first (using the console for I/O) and only adds the GUI later. As a new programmer, I found it to be tremendous both for learning and (since the index is excellent) for reference as well.
I had previously used Visual Basic, Step by Step to learn VB and that book seemed to be good as a learning tool but the index was so poor that it really didn't work well at all for reference, which put me off the "Step by Step" series, which may be unfair because the C# book might not have that shortcoming at all.