I am not personally aware of any "C# For Beginners" that actually start from a 0 programming knowledge standpoint. Seems to be the majority (if not all) reference material on C# assumes that you are coming from C++ or Java and have a general understanding of programming techniques and verbiage before getting started.
C# is not a good "first language to learn."
I have to disagree with you both on this one. While I feel other languages especially those that are interactive such as Python are perhaps a better choice starting out, I don't believe learning C# first is a bad choice. Suggesting that one learns C++ instead of C# because of C# being multi-paradigm seems even moreso hypocritical, considering that C# confines you more than C++ does in that way.
As for the OP's question, there are plenty of beginner C# tutorials and reference material you may find doing a search query on Google. I would recommend when looking at books on Amazon you also check reviews from programmers on said particular book. Don't necessarily rely on the reviews that are posted on Amazon itself.
I will however recommend if you are just starting out that you try Python. Many will argue that it is a much simpler language (though no less powerful) than C# and I agree whole heartidly, however my primary reason for recommending it is because of it's interactive prompt. This will allow you to quickly try new things that you have learned and encourages experimentation. When learning to program you won't learn just by reading but by further experimentation, and this format works well for that. There is also an excellent free online book, http://greenteapress.com/thinkpython/thinkpython.html, which is a great introduction to Python and programming in general.