Blue couch would be the best lawn as buffalo needs too much water and thats something you dont get up there is rain. If its natives you want to grow I cannot help you very much as all the grevilleas I grew there did not survive. The only way you are going to get good soil is to keep adding compost and animals manures I would work the soil first and get it a bit better before planting anything as its heart breaking when they just die, so prepare your soil first, grow a cover crop I used to grow cow peas in it ( you can get them at the produce store in Flinders Street ) if its still there, then just dig them in, start a compost pile it wont take long to mature in that heat.

I use to buy most of my trees at the Sunday Market there was a guy who used to grow heaps of natives and exotics and cheap they were too, also try the Showgrounds market plenty of bargins there and the people that sell them you give you lots of advice.

There are plenty of trees that would be ideal for you but how big do you want them what size is your block apart from the Delonix regia ( Poinciana ) Illawarra flame tree, Tabebuia, Cassia, for the flowers there are lots that are shady have a look around your area and ask the neighbours what there names are, if they can grow them so can you, admire their plants and they will give you cuttings.

Hibiscus grow well there Syzygium or Lily Pilly, Poinsettia, Snowflake all Euphorbia do well, pentas, Leptospermum Tea Tree and bougainvillea they are some of the ones I grew there and dont forget the Cycads Sago Palm I hope this has been a bit of help to you....Cheers..MM.