Australia does not need a head of state, and neither do its states or territories. Not some hand-me-down arrangement from the Poms, not a President either (elected, appointed or whatever). Australia and the states are bigger than any individual and government should be structured accordingly. The Governor-General of Australia and the State Governors are irrelevant, and their ceremonial function becomes all the more hollow the less relevant they become. It's time to amend the Constitutions of the Commonwealth and the states in order to remove gubernatorial positions.
The current batch of viceroys - like Her Maj - aren't doing a bad job, but they are doing a non-job. Australia's current Governor-General is often represented as a rorty old figure from Gilbert & Sullivan, all epaulettes and campaign medals, while his defenders say he's an eminent person you can be proud of. They're both right, but if you read The Major General's song he is telling you directly how eminent he is, while at the same time being completely irrelevant.
Former Governor-General Sir Ninian Stephen said that the viceroy should 'represent ... the Australian nation to the people of Australia', but a good writer holding no office whatsoever will beat any public official at that. There are basically two roles performed by the Governor-General and the State Governors (and I include here the Administrators of the Northern Territory, Norfolk Island and whatever other equivalents exist in other territories), administrative and ceremonial.
First, the administrative role: they rubber-stamp parliamentary bills and regulations on advice from ministers. Cabinet decide the form of regulations and when bills will commence as legislation, so the next step of "vice-regal approval" is irrelevant. If an unconstitutional law or regulation is passed, the High Court strikes it down and "vice-regal approval" counts for nothing. Any other governmental process that added so little value would be cut out of the budget.
Second, the ceremonial: they open fetes and give out prizes. In the case of the incumbent, the Prime Minister has basically elbowed out the G-G and does this stuff himself. It is, as Menzies said, what politicians excel at: giving away things that do not belong to them. The theory goes that you might not want to accept a gong from a particular head of government, so a harmless old governor takes the political edge off. The fact is that there is no way of taking the political edge off a gong, if the government wants to give one to someone they'll do it to make themselves look good - and if you don't want to be made a political tool of, say that you'll refuse to accept it and call a press conference during the award ceremony. The next Prime Minister and the one after are extremely unlikely to revert to convention. If you must, the Australian of the Year is eminently qualified to do the ceremonial stuff, and no threat to the elected government.
The State Governors (including the territories etc.) can be done away with by legislative change. In NSW this is a little more difficult thanks to Lang's Game, but a well-informed referendum should yield the right result. One little piece of legislation amending the state constitution or the statutes governing the territories, and one last letter to London saying: we won't be asking you to rubber-stamp any more heads of state, but thanks anyway for all those duffer rear-admirals and useless nobles.
The Governor-General has two other roles that the others don't have: commander-in-chief of the armed forces and constitutional umpire. These are not merely niceties or relics and must be dealt with properly.
The Chief of the Defence Force is actually the commander-in-chief of the armed forces. He acts under direction from government and in the name of the Governor-General, but it is this position which is at the head of the command structure and the Constitution should reflect it.
As for the constitutional umpire role, e.g. 1975: that could be done by the full bench of the High Court. Whitlam sympathisers fulminate over Barwick's behind-the-scenes role in 1975 but the full bench would be more learned, relatively pluralist and open than the case at the moment. The model - even though they got the result wrong - is the US Supreme Court in Bush v Gore, and I agree with this eminently Australian solution to an impasse like that.