Three approaches are possible, all variations on getting a signal to a media streamer. Lots of media streamers exist, some DO support HDMI out up to 1080p. I like the netgear stuff, which is pretty reasonable and fairly dependable.Specifically, look at the EVA800. It supports HDMI and other standard outputs (your hdtv may too), so connection to a stereo receiver with standard RCA interconnects should be easy. if you can throw down for it, the Slingbox Pro is better for a number of reasons (like a really slick remote access interface).
Regardless, the media streamer needs to talk to your computer, and that's where your choices come in. Best in my book, run an ethernet cable (cat 6 ideally) through the attic/crawlspace. This is the cheapest and most dependable way to go, but as usual involves the most work. Second, WiFi- 802.11(g or "pre-n" if your KNOW there won't be compatibility problems- still dicey) from a wireless router at your computer- most common, but also most prone to interferance and the potential for a loss of picture quality. Third- if your house isn't really huge, you can use powerline ethernet adaptors- this is pretty expensive, and generally only done when there's no acceptable way to install an ethernet run. Again, netgear's a decent example- google HDX101; you'll need two (one at the computer, one at the media interface). Their transmission rate is listed as 200 mb/s- half that would support what you need to do. Your friends are totally right about the hdmi distance and s-video quality issues. One more thought: You CAN install wall plates for network ports- Belkin and a bunch of other folks make them, but ideally use BASEBOARD mount jobs, which are about a fifth the work of a wallmount ports (think: hole saw, mollies, level, maybe hit a stud, plumbing, electrical wiring, etc). With a baseboard port, you can also cut and pull the wire, seal the little holes for the wire and screws, and nobody will ever even know it was there- wallmounts leave BIG holes.
Who knows what you'll need ten years out?