The main difference, aside from syntax, between the old way of coding you've done and the new, is objects. You have to learn to think in terms of objects and object modeling. If you can't do that, no amount of rote syntactical education will help you.
I'm not really a big fan of Java for most things, but hands down the single best, most approachable, most relevant introduction to object oriented program is Kathy Sierra's book "Head First Java". It's one of the only textbook style programming books I've ever found readable enough to just sit down and go through in order.
Once you understand objects -- including inheritance, polymorphism, and so on -- then you're at a place where the specific languages vary mostly by the libraries available for them and their syntactical differences -- which are easily overcome. C# and Java are extremely similar so I'd start with one or the other. C++ is still the real deal, but both C# and Java let you work without having to manage memory so damn carefully.
Starting with Java over C# will, IMCO, give you a better feel for best-practices because the MS Visual Studio IDE tends to push you to draw your screens and dialog boxes first, then hide code behind events and buttons instead of starting with a functional object model and then using the UI tools to build an interface and call back into your real objects. C# will probably take you further in the employment market, but learning Java first will make you a better C# programmer.