Brisbane to Paris is pretty specific! I haven't done that but have used a few different carriers between east coast Australia and Europe, including QANTAS, Singapore, British Airways, Air New Zealand and Malaysia Airlines. I have also flown legs with Finnair, AirAsiaX and Virgin, and some internal legs in Europe on SAS, Ryanair and Easyjet.
Everyone will have their own views on what makes a reasonable experience, but you are going to be flying for 20+ hours. If you can take advantage of the sales on full service carriers, they won't be much more expensive than the cut-price carriers, and much more comfortable.
None of the airlines I have flown on to Europe has ever lost or misplaced my checked baggage.
While I wouldn't recommend a particular airline, I would suggest that if you start to want to do more than a simple return ticket, go to a travel agent. It will cost a little to do that, but I have found it has been worthwhile in getting the right fares and connections for more complex itineraries.