Budget = cheap? = camping. Well for the country areas.
Size - OZ is about the same size as Europe, with far less people.
When - the climate will select what areas you will find comfortable (summer head south - Tasmania is good then, winter head north)
Roads - sealed tar - limits your options!
Good dirt - opens up most sights
moderate dirt - all major and minor sights.
Sights - natural, measums, history etc ...
You have given us how long .. but not what your interests are. In 4 weeks I would not try to cross the country - you'd not see that much unless you stick with fast tar. Your on holiday - relax and take your time. I spent 8 months running around europe.
Regards Frank Warner
motorcycles BMW R80 G/S 1981, BMW K11LT 1993, BMW K75 G/S