The scenario: I'm cycling/hiking through Aus and get an emergency call to fly somewhere, what's the furthest out (in kilometers, as the crow flies), that I could be from a regional (ie, Port Lincoln) or major (ie, Adelaide) airport?
A little over 600 km, based on a list of "large and medium airports with scheduled services".
You can use the World Airports Voronoi Diagram to get an idea. Each cell of this diagram is the region that is closer to the airport within it than to any other, and so the point furthest from any airport must be at one of the vertices of this diagram, equidistant from three airports and further from all the rest. One could manually check them all, but eyeballing, I think it's the point equidistant from Ayers Rock, Broome, and Newman. That distance should be slightly more than half the straight-line distance between Ayers Rock and Broome, which according to Google's distance tool is 1209 km.
(Of course the answer will depend on exactly which list of airports you use. The WAV page notes that their diagram is based on a list of "2,980 large and medium airports with scheduled services", taken from https://ourairports.com/data/. The main data file there,
airports.csv, currently contains about 58000 airports, so presumably they're using a subset. The Voronoi map is also dated 2015 so may not reflect any airports that have opened or closed since that time. However, the diagram does include Port Lincoln so the airports it lists may be roughly comparable to those you want to consider.)