Correct me if I'm wrong, but GTK isn't really native on anything but Gnome. Instead apps are just skinned to (mostly) look like each platform.

Yes. GTK on Windows is borderline useless unless you pour significant effort into optimizing your program for it; and under OSX no amount of effort will make it feel anywhere close to native.

I wonder how Deluge looks/feels on Windows or OS X. I've heard only good things about its native looks, but haven't ever used it on anything but Linux.

It looks OK, but it is easy to see that it is not native: http://i1-win.softpedia-static.com/screenshots/Deluge_1.png

Gtk doesn't use native controls. While grandparent didn't mention that detail, I think it's the deciding factor here.

Gtk (at least from 3 onwards) doesn't even aim to be cross-desktop on Linux, let alone cross-platform. Meaning, your gtk apps will always look and behave according to the Gnome conventions on all platforms, which could be what you want, depending on what cool-aid you're drinking ;) .