Connair (no, not the movie airline) from Alice Springs to Ayers Rock. A DC3 back in 1978.

And, although not really in the Outback: Bush Pilot Airways from Cairns to Lizard Island. A BN-2 Islander also in 1978. This was a very memorable flight. On the return we flew very low over the Grreat Barrier Reef and got to see a whole lot of it.