There's the Russell at the Rocks but I think the prices have gone up in recent years. Also Pensione in Pitt St has had good reps. I've stayed at the first, though some years ago, and have had a few friends stay at Pensione. Both good.
Seriously, I stayed at a B and B in Paddington, in a very nice house. It was $85 AU a night, your own room but shared bath ( if anyone else is there, she only has 3 rooms). Two minutes from the bus on Oxford Steet, Darlington is a 20 minute walk or 5 minutes on the bus. Bars and resturaunts an easy 5 minute walk.
The woman whose house it is makes a nice fruit-plate for breakfast along with coffee ( thrown in as part of the $85 ). I can give you details if you want, feel free to pm me.
I stayed there 2 weeks and quite liked it.
