Ah, it's called "Embed Color Profile" on your version.
Sadly I don't know which are the good labs in Sydney. There must be plenty, though.
The classes are right here on the website.
Yes, it's perfect, great.
It should be right there, in the save dialog.
Do you mean in Photoshop? No, definitely not Custom. It must stay on "North America General Purpose 2".
Yes, Raw Class first.
Which part of Australia do you live?
Ok, can you choose the one with the least "busy" detail in it - eg clear sky and smooth water - and see if you get the same poor quality when you save?
http://www.damiensymonds.net/2015/08/about-jpeg-file-size.html