It's very easy, this was by far the easiest radio I've ever replaced (I have a '95 LE). Just pop off the U-ring and there are four 10mm bolts holding the radio in. Remove them and it's out. If I were to go inside your car with a 10 mm socket in my hand (with an extension, one of the bolts is back a little bit), I could have your radio out in 60 to 90 seconds, and that's a conservative estimate. And assuming your CD changer is right under the radio, that would come out at the same time (same four bolts).
The CD changer would be replaced with a pocket (a plastic hole), useful for storing small things. And don't worry about losing your CD changer, CD changers are obsolete - compressed music is where it's at these days. The radio I put into my car is the Sony GT410U, it was cheap and works well. The feature I like about it is that it has a USB port on front, I just plug in a flash drive to listen to music / podcasts. I just hook the flash drive up to my computer to swap out files. The model I have is the Sony GT410U.
And if
www.crutchfield.com will ship to Australia at a reasonable price, go with them, otherwise look for something in Australia I guess.