Here is a circle of radius 2030km centred at 26S, 133.35E (on the Northern Territory/South Australian border of Australia). I used this tool to generate it.
This is a reasonably close approximation to the smallest circle containing all of mainland Australia. It is interesting that its centre should lie on the border. The three points closest to the circumference are the NSW/Vic border, Byron Bay (the easternmost point of mainland Australia) and about 75km SSW of Exmouth. There are also three other parts of coastal mainland Australia close to (within 75km of) the circumference, notably, near Dirk Hartog Island (WA), the south west coast and Cape York (Qld).
Hence one can almost say that 6 points of coastal mainland Australia form a cyclic hexagon whose circumcircle is the smallest circle containing mainland Australia! The largest distance I could find between two mainland points of Australia is 4048km, suggesting that Byron Bay to the point SSW of Exmouth is not too far from being a diameter of the circle. However due to spherical geometry, its midpoint is actually quite some distance south from the centre of the circle shown above.
Note: I tried a circle around Australia including Tasmania, but it wasn’t as interesting – only 3 points close to the circumference. 🙂