Start on Petzold - definitely agree he's *the* place to start. Programming Windows should be on every Windows developer's bookshelf - even if they do .NET apps - just so they understand what .NET does under the hood at the moment. It'll teach you a broad swathe of Win32 UI development stuff.
Move on to Jeff Richter's series of books Programming Applications for Win32, Advanced Windows Programming, and Programming Server-side for Windows 2000. These will teach you pretty much everything you need to know to make Win32 logo-ready robust multithreaded applications and services.
If after that you fancy seeing some history - Brockschmidt's Inside OLE book is the COM/OLE Bible. Books by Don Box and Chris Sells will help turn that text into practice. For MFC Jeff Prosise and Mike Blaszczak both wrote excellent books.
If you're interested in moving on to deep .NET programming, I'd suggest you'd get a lot more mileage by knowing Win32 API too - but to dive straight in and pick a language - most have CLR/.NET equivalents. If you know Java (or to some extent C/C++) take C# - you'll find it really easy to get into. Eric Gunnerson's book is a great intro to C# syntax - and Jeff Richter's Applied Framework book is pretty damn good intro into calling .NET Framework types.
As for the other flavours .NET languages - I'm not so sure - but I've no doubt that you'll be able to find something to meet your tastes. Most of the books I'd recommend have been written by people who either work or have worked at Microsoft on the languages - they have less regurgitation of MSDN, more original information.
I have most of these on my bookshelf still - and one or two are still in good use even after moving on to CLR/.NET development around 4 years ago.