I regularly fly with my 60lb Vizsla in the back of my 360. 

 

 I got him a harness marketed for securing large dogs in the back of your car.  My harnesses attach to the overhead hardpoints, leaving the phenolic hardpoints in the aft bulkhead available to attach the dog.  A U-bolt anchor on each side, 3/16" cord from REI between the two, and an 18" long "shockle" made from 1" tubular webbing and bungee cord keeps him secure in the back but free to stand up and turn around.  I made the shockle, but I know you can buy one.

 

I use large mutt muffs on the Vizsla.  I have medium muffs for my 65lb greyhound (also fits in the 360, but being a greyhound is awkward as hell).  The dogs resisted them at first but now they'll keep them on for the duration of a 6hr flight.  Before Ive cleared the runway after touchdown they strip em off.  The muffs must be doing something positive for them.

 

Your dog wont need 02.  If your only responsibility is sitting in the back seat, you are fine below 25,000.   At 16k cognitive ability might be reduced and the pup might have an easier time sleeping but no harm done.

 

Joe Cz

N424DH