Those are probably your best options. I've set up a couple of media streamers for friends, and they seem to do their job reasonably well. The 360 option is a good idea; as you say you get the benefits of a games machine too but the only caveat their is to stream movies/videos the PC must be running Windows XP Media Centre edition or Vista home premium/ultimate. I'm pretty sure that XP home and Por will only stream music - but I could be wrong there, things may have changed.
PS3 is another option - but at this time the most expensive one - it's a personal preference over which machine you prefer, and for me to state one over the other will result in lots of rabid fanboys tearing into each other with their views. Not unlike the great PC vs Mac debates.
One other option - a number of external hard drives now come with media players and connectors built in, so you could use those to store your videos and simply plug it into the telly - with the added benefit of being able to take it elsewhere with you too. I know freecom do one or you can buy a hard drive enclosure with the sockets/firmware and controls and make use of an old hard drive.