If this were the case, I would expect OTL's Aboriginal Australians to be exceptionally intelligent, on average. Maybe that's the case, but I suspect that they average about the same as other groups of people.
I base this on one theory that changing environments in Africa was one of the factors that selected for intelligence among humans.
Homo sapiens are already smart enough that they don't need to get particularly smarter to survive in Australia, or at least, the trade off for having even bigger brains (nigh-impossible births, lots and lots of food to fuel the brain) isn't evolutionarily worth it. Early hominids, on the other hand, may still select for larger brains under the greater pressure, and the downsides will be outweighed by the benefits in *Homo australis just as it was for Homo sapiens.
For the question of size, getting Homo erectus to Australia before they went through the island dwarfing could produce a reasonably sized intelligent hominid, as Australia has not triggered island dwarfing in animals that have ended up there.
I agree, though, an entirely different species could very well have it worse than the Aborigines of our timeline, terrible as that would be.
EDIT: Though depending on how immune they are to human diseases, they could put up a stiff resistance to human invasion. Primates can be affected by flu, tuberculosis, and the common cold. But what effect would measles or smallpox have on *Homo australis?