I spent the last week or so working on a project that I call HoRNDIS (pronounce: "horrendous") -- a Mac OS X driver that allows you to use your Android phone's native USB tethering mode.
It's a kernel extension, and requires NO software installed on your phone, and NO background apps on your Mac; if your phone supports RNDIS tethering, you're good to go! To make you salivate a little more, it looks like this when it's running:
I've tested it on my machines, and a few of my friends have tested it on their machines, but it hasn't gotten *hugely* wide testing yet, which is why I'm still tagging it as a [BETA].
If you're interested, give it a shot... you can grab it from my web site, and if you're so inclined, get the source on GitHub, too.
Let me know if it works for you!