First things first: there is Objective-C, which is a programming language, and there is Cocoa, which is a framework for constructing OS X applications. The former is roughly comparable to C#; the latter to .NET.
You can, if you wish, write Cocoa-based applications in languages other than ObjC; for example, Leopard includes Cocoa bindings for Python and Ruby as standard. The only downside of that is that the currently available documentation almost always discusses Cocoa development purely in terms of ObjC, so in practice you still need to know a bit of ObjC (enough to read it, anyway), in order to do this.
Second: whatever language you use, you will absolutely need to have reasonably decent object-oriented programming skills to write Cocoa applications. If you don't already have OO skills, I recommend you develop some ASAP, ideally before jumping into full-on Cocoa development. Cocoa is a very dynamic system, so a highly dynamic OO language - Python, Ruby, Smalltalk, etc. - will stand you in better stead than a relatively static one (e.g. C++, Java).
Languages such as Python and Ruby also have the advantage of being interpreted rather than compiled, so are faster and more forgiving to learn in. With plenty of literature and community support available, you shouldn't have too much trouble picking one of these languages up. I'd also recommend reading some general programming literature if you need to sharpen your skills a bit; Steve McConnell's Code Complete is a must-have in my experience, and no doubt other folks can provide suggestions as well.
Third: if/when you have some basic OOP experience under your belt, picking up a bit of C is also a good idea if you're going to be using ObjC. I think Kochan's ObjC book includes enough C to get you going (although I haven't read it myself), though most other books on ObjC/Cocoa development assume you already have that knowledge.
You do need to understand C pointers (which actually aren't that hard to grok as long as you find a good, clear explanation of them to work from, although they will take a bit longer to become second nature). Other stuff like C-style memory management and string handling I wouldn't worry about beyond being aware they exist since ObjC makes its own very thorough arrangements on those fronts.
Fourth: yeah, that first step into Cocoa is a bit of a jump. Wrapping your head around all the concepts involved takes some time and work; Cocoa really likes its abstractions. Stick at it though, and once all jigsaw bits snap into place you'll find it definitely pays off. Read around the Cocoa literature and various online resources, tinker with existing sample projects, write your own simple apps to explore individual concepts and test your understanding of them, and don't be shy about asking when you get stuck.
Fifth: in case all of the above sounds like a lot of work and just a bit intimidating, if it's any reassurance I'm totally self-taught myself with nowt but a fine art degree by way of formal qualifications. Yeah, it takes a bit of time and sweat, but it's eminently doable and it's a pretty sweet nut once cracked.
Finally (and maybe I shoulda just put this first... oh well): while you're correct that VB itself isn't available for OS X, there is a commercial cross-platform VB-like language/environment that is: REALbasic. So if you like VB and really want to stick with a VB-ish approach, you might want to check it out.
HTH, and best of luck.
