Receiver features
Snake,
HDMI is more convenient in that it carries the audio and video signals. You can still take advantage of 1080P over HDMI by connecting the source (BluRay, HD-DVD, etc.) directly to the 1080P display. You would need a seperate digital optical or coax connection to carry the audio signal to the receiver.
If your receiver budget is <$500, I would consider a quality receiver without HDMI like the Yamaha RX-V659, or maybe a refurbished model w/ HDMI (RX-V1600 on Ubid.).
If you are willing to pay $1k or more, the mid-fi models from Yamaha, Denon, and Pioneer all have plenty of audio and video features. In the next 6 months, you will start to see new models which include HDMI 1.3