It's very likely that I have a different view from most on this issue, given my strong feelings about platform native user interfaces and controls/widgets, but I very much tend to prefer your second approach. Even I'm not masochistic enough to go through the hassle of building the entire application separately.
So I would definitely write the library or data layer code entirely separate from the GUI layer. Doing it in C++ is an obvious choice, especially if you're already comfortable with that language, but more on that later. The point is that this code should be limited only to your "business logic", and thus completely platform independent. If you follow solid object-oriented principles, it should work out that the bulk of the programming work is done on this level.
Separately from that, you would write a thin, "wrapper" library over the core OS and UI functions for both Windows and OS X. The wrapper library would be the sole entity responsible for directly interacting with the platform, and your data layer code should call functions from this wrapper library, rather than directly from the platform's API.
Of course, several of you reading this are probably screaming "But that's what QT already does for you!" Yeah, I know. But it doesn't use native widgets, and it doesn't conform to standard platform conventions in so many places. That means it sucks. I've seen other wrapper libraries for Windows that do get this right, but I've yet to see one on OS X that looked halfway decent. Yes, I'm picky, but so is your typical Mac user. They just won't put up with the type of garbage on their screen that Windows users will, and even the Mac Office team knows this. (We all collectively applaud you for trying to get this right.)
As far as your choice of languages, you say that you are looking for native code on both platforms. That's a pretty difficult blob of jelly to pin to the wall. For example, do you consider JIT-complied code to be native? If not, that rules out C#. Excluding any type of interpreted code rules out a host of other potential languages. You aren't left with many options other than C++ and Objective-C. But C++/Win32 programming isn't that much more difficult than Cocoa programming, just different.