I spent some time in Perth and, though lovely, I wouldn't recommend it for a week. It actually reminded me of San Diego - it was beautiful, but it wasn't the most exciting place in the world. However, Freemantle had some interesting things and the day I spent on Rottnest Island ranks among my top five travel memories anywhere.

I'd listen to the people who suggested Hobart, but if you decided that it was a bit too far, I'd go up North. However, you could probably also have a great Outback experience... a couple of nights in Uluru and a few more in the Alice area.