I bought my last desktop over the net from AusPCMarket who used to have their shop in gladesville but now is in Silverwater or somewhere around there.
http://www.auspcmarket.com.au/
They will assemble it for you and have a range of pre-defined systems you can choose from (click the "systems" link on the home page).
Their website is always up to date on prices and while it's not the 100% cheapest around it is competitive since all their prices include delivery.
As far as spec goes, I went with a dual core AMD 64 and i throw quite a lot of shit at it and it still goes damn fast. Dual cores mean you can be playing a game and alt-tab and you still have an entire cpu core to work with in the background.
As for motherboards i can recommend anything by DFI, the more you pay the more features you get. These are designed for gamers pretty much.
I got a 19" Benq LCD with it and its pretty decent although of course the bigger the better and the Dell 24" LCD is looking pretty good these days if you can find it on special.
1gb memory at the very minimum and SATAII Hard drive(s) as big as you can afford. With the memory, try going for a brand name matched pair of modules (like Corsair) since im pretty sure most chipsets access memory faster in pairs these days.
The video card is quite important whether you play a lot of games or not and spending more is better. For under $500 you can have a GeForce7900GT that will handle anything you can throw at it today and for a while to come. PCI-E x16 (replaced AGP) cards are what you want to look at, making sure the motherboard you choose has the capability to use them.