Unwired Internet offers free wifi in various cafes and public libraries around Sydney.
http://www.unwired.com.au/get/storefinder.php?p=3
There're plenty of Internet cafes, particularly around Chinatown. Convenient stores often have a few PCs for hire also.
As mentioned, McDs and (some) Starbucks have free Internet too. McDs have a limit for 50Mb per day, I think.