As an expat to Australia who was in the same situation recently, I can't say I found any meaningful differences between the profits and the notionally non-profits, they all quack like ducks and walk like ducks to me. Neither have I found much difference between the insurers I've tried, although given the choice I'd steer away from Medibank, it's government-owned and thus even more bureaucratic, slow and incompetent than your average insurer.
If your employer has a corporate private insurance plan (and they mostly likely do), it will usually have better rates than what you can get alone, so you're probably best off with them, regardless of who it is.
Also remember that you don't need private health insurance, Medicare covers all the basics except, bizarrely, ambulances and dental. The main reasons to get it are if you're planning kids and would prefer a private hospital, or if you're earning enough that the Medicare levy surcharge (up to 1.5% extra tax) would otherwise kick in.