It was actually a Great Cormorant (Phalacrocorax carbo), a widespread native to Australia.
Birds are most closely related to crocodilians, in the dinosaur clade archosauromorpha. (Reptiles, thus, are paraphyletic - not really a true, complete evolutionary grouping, and rather just a description).
But let's take it from the top. Or, at least, the beginning of the mesozoic (the "middle", or dinosaur era of 250 - 65 million years ago). Archeosaurs (the precursor group to archosauromorphs) arguably became more successful at the time than synapsids (mammal ancestors) because they were better suited to the dryness of the Triassic period (250 - 200mya). They included dinosaurs, crocodilians, and the ancestors of birds. Crocodilians first appeared about 84mya (late Cretaceous). Modern birds (neornithes: feathers, no teeth, hard eggs, several flight adaptions) evolved into a variety of forms in the Cretaceous (145-65mya). The two bird groupings, palaognathae (comprising ratites - most of the flightless birds - plus the barely-flying tinamous) and neognathae (the rest) probably arose before the KT meteor event of 65mya, but radiated into the numerous different species mostly afterwards.
Now, the reason that cormorant looked a bit duck-like to me was its webbed feet and the shape and size of its body. But they are not related at all. Cormorants have been grouped together as pelecaniformes (which includes the pelican's family pelicanidae), while ducks are in the anseriforme order.
Although Colin Tudge (in The Variety Of Life) is happy enough with the cormorant's above classification, Wikipedia casts doubt on pelecaniformes being a true clade (that is, a single complete evolutionary grouping), and suggests phalacrocoraciformes as a more properly monophyletic clade. The issue here is that the pelecaniforme was used to encompass all birds with fully four webbed toes. But as we know, classification based on such a stark physical trait is dangerous, since the various species could easily have evolved separately but convergently. If the purpose (webbed feet for paddling) is so clearly useful, that evolutionary change could have happened several times, several locations.
The names cormorant and shag are sometimes used interchangeably, but even when each is called by its proper name, there is no consistency between them. Their collected family name is Phalacrocoracidae - but the discussion there concludes that this is not one consistent evolutionary grouping.
The cormorant I encountered was not well, if it was so near humans. It was wandering around, not flying, and unlike the one above had most of its tail feathers missing - and appeared far too tame for its own good. It and kids were a danger to each other. I contacted the wildlife rescue organisation WIRES, who recommended taking it to a vet that was on the Wires register; so I took it to Struggletown in Randwick. Unfortunately, it died within the next two days - as a result of lead poisoning. How? Unknown, and this was not the first bird specimen to be sent off for analysis for this issue. Also not known what the missing tailfeathers had to do with its plight. I was told the apparent tameness was due to lack of interaction with humans. Still, it was the indirect effect of human activity that got it in the end.