Given that it's Australia's national dish, it's actually kind of hard to find restaurants serving roast lamb, presumably because it's slow to cook and rather expensive these days (lamb prices have more than doubled in the last few years). Lamb shanks, on the other hand, feature on the menu of virtually every casual eatery in Australia.
(Sunday roast with lamb, by "Sir Thomas Napier" on flickr)
But the best place to look is definitely a pub, aka "hotel" in Australian. The British "Sunday roast" survives in Australia as well and a great many, but by no means all, hotels put on Sunday roasts that often feature lamb. Here's a random selection in Sydney from Time Out, although you'll note that not all are lamb and many are "continental" rather than Australian/British in style, because Sydney's a bit too hip that. And here's another top 10 of more classically English-style roasts, although again, many seem to focus on beef.
"Clubs", the odd Australian institution of gambling joints thinly disguised as sporting or veterans' clubs, also frequently offer Sunday roasts, but the quality of the food tends to be disappointing. (I'm painting with a broad brush here, and there are exceptions both ways.)
(Traditional Argentinian Carne al asador, by seretide, Wikimedia Commons)
All that said, the best lamb in Australia I've had was grilled by my Argentinian ex-boss, and the 2nd best is served at Argentinian joint Porteno in Surrey Hills, Sydney. The process of roasting it crucified on a metal stake looks a bit like something out of a horror film, but hot diggity dog is it good. Probably not quite what you were looking for, but hey, multiculturalism is also very Australian these days ;)