If you didn't do this as soon as it came out of the box, save the configuration and then, do a hard reset before updating the software- it's what the people from Denon/Marantz told us to do at their training sessions. Then, verify the polarity of the speakers, by connecting a battery at the AVR end of the wires- not accusing you of anything, I'm just trying to make it possible to KNOW the polarity, rather than assuming it's correct.
Test Audyssey in the first listening position twice, not once. Test the other positions as usual.
I have never heard a Denon that sounded bright- in fact, I used to think Yamaha sounded a bit thin before Avantage. Not sure if I prefer YPAO to Audyssey, but I have used the latter successfully many times but that doesn't mean I thought it was perfect or that I didn't tweak it a bit.
Glad to see you got it to sound better.