From what I've been told, the sound through the optical is equal to what you get with the HDMI. The HDMI helps simplify the connectivity by running both uncompressed audio & video signals. Also, I've read that HDMI uses a little less than half of it's capability, so it should be the standard for the foreseeable future. So, you'll probably want to get a receiver with HDMI. Also, you mentioned DVI on your tv. Well, HDMI is backwards compatible with DVI, all you need is an adapter. I know that the Yamaha RX-V1600, RX-V2600, and the Pioneer Elite VSX-72 & VSX-74 have HDMI. I believe the Deneon 3806 does as well. But I think the cheapest is the RX-V1600 with is around $800. The others are at least $1K. Good luck. I hope this helps.
EDIT: Sorry, just checked the Yammy website. The 1600's MSRP is $1,099.00. So, they're all above $1K. Well, if you can stretch your budget a little, it would be well worth it. Also, check around. It is Christmas time. Your local electronics store may have a sale that might knock off $100 bucks or so.
Yamaha has an HTR 5990 that is $999.99 at Best Buy if that helps & it does have HDMI & all the other connections you need.