If the Denon 3800 is out of the question, then your best bets are either going to be the upcoming Pioneer Elite unit with 7.1 multi-channel output, or the upcoming Sony PDB-s550 which will also include this feature. You will get all the necessary internal decoding for every music format currently available on Blu-ray or DVD, and both units start under $1K (well the Pioneer is $999.95).
FWIW, none of the current Pioneer or Sony Blu-Ray machines boot up very quickly, which is honestly the most annoying thing ever (at least for me). I've stop watched the Sony BDP-S300 at around 45 seconds, with similar times for the Pioneer Elite 95 unit. On the flipside, the Denon Blu-Ray Transport (DVD-2500BTCI) boots up in a mere 18 seconds. While this is still signicantly slower than almost every DVD player on the market, it was a vast improvement over the Pioneer and Sony units. Additionally the Toshiba HD-A3 unit, the final iteration of HD-DVD, takes around 30 seconds to boot up, which I think is definitely an improvement from the 2nd gen. Blu-Ray units, but still not acceptable for a high end HT device.
Now, I do understand that the Denon 2500 is not really an option for you due to it's HDMI exclusive output, but I thought I'd mention it just as a reference point for you. Unfortunately I do not my own personal boot up time trial results for the full fledged Denon 3800 player.
The new Sony unit promises better boot up times, but how much better is still unknown. I do not know what the new pioneer units claim.