To be perfectly honest, it doesn't make a huge amount of difference what programming language you start with - the stuff you'll have to learn before you start making functional programs is the same. All programming languages work in a similar way - at then end of the day all they are is an abstraction of writing actual machine code. The only real difference is what the language offers to you. Learning C# or Java is a good first step because they are memory-managed, garbage-collected and have very, very strict compilers. Languages like C++ don't have these facilities because they are optimised to be as quick as possible, which can make them daunting for beginners. What matters is what you want to do. Do you want to be a multi-platform programmer? Learn Java. Do you want to develop for Windows or Windows Phone and use a world-class IDE for free? Learn C#. Do you want to develop rich, web-based experiences? C# or Java works for this. Do you want to be a games programmer? I would suggest learning C# and XNA to learn the functional side of games programming, and then if you want to get more technical move on to C++. The real lesson is that no programming language is a bad place to start - once you know one, picking up the others is far easier.
I don't think you need classes to start out. I'm not a professional in the field but I know my way around a few things, I started with VBA in excel and word due to work requirements, this gave me an idea about object based programming and variables etc you can do some pretty awesome things quite quickly that make you look like a God to non teccie users. I then got bored in work and decided I needed to teach myself something else, so I found http://www.w3schools.com/ and looked at HTML and CSS although not programming skills that led me to ASP.NET and then to now where I'm loving C#. I can build basic applications and am pretty happy with what I have learned (Google and MSDN being the main sources) to take it further I think that now is the time to buy some books and maybe find some night courses. As I haven't learned the boring stuff like making your code secure and efficient.
Admittedly no, but you should start learning them not long after starting. As soon as you get program flow, variables and general imperative program structure you should move on to classes simply because how powerful and useful they are in modern software development. It's not that boring
A good book and a friend that gets you kickstarted by REALLY explaining what a class, object, variable and method/function is. Some patience, google-fu and a goal help lots too. By a goal, I mean a small project that you work towards, learning the language as you go. The first is a "hello world" program (mandatory), the second could be something like a small tool that lets you keep score. Something with two buttons(+1, -1) and a display. The third could be a simple chat/mail client and by then you should be acquainted enough to read something about design patterns and realize you did it all wrong in your previous projects.
