I rang a trans-friendly health clinic and asked if they had any docs that were experienced with trans health. All of the docs were, so I was able to ask for a specific one from then on. The place bulk bills if you have a Medicare card as well as a Healthcare or Pension card, otherwise there is a cost per appointment (not sure on how much it is). I don't know if I'm allowed to say which place it is specifically, but it's in Darlinghurst.
Things didn't work out the way I planned as I was late thanks to our GPS and roadworks all up the coast. I ended up seeing a different GP to what I had orginally booked. When I went in, I explained why I was there (that I identify as trans, that I wanted HRT and that I knew I had to see a Psychiatrist). The doc asked some questions and I answered them to the best of my ability (I have memory and anxiety issues). I received two referrals to different Psychiatrists, one that was covered by Medicare and one that wasn't, as well as a request to book another appointment there, I did. Being in Sydney you'll probably have more options in regards to Psychiatrists.
I also received blood tests, but I'm not sure if that had anything to do with HRT or if it was more to do with something else I asked about during the appointment.
As for how I knew the place was trans friendly, it was a mix of three things. A list from FTM Australia, a google search and a print out of contact details given to me by the therapist I saw at the Gender Centre.