Ahh I forget, these are my anime files. I had a lot of .mkv files that needed to be converted to .avi for streaming, otherwise I got a network error. For "normal" videos, you are correct.
Tversity will transcode those .mkv files automatically as long as the transcoder is turned on. I don't think I've ever run into an .avi file that the PS3 wouldn't playback natively.
As far as what's needed to connect:
Just get a router, it will reduce the amount of headache in the long run. 90% of the problems we see for streaming media are due to network issues and people trying to cheap out. It sounds like you will be able to wire everything together, which is very good. Go to NewEgg and just find the cheapest router that gets 3 stars or more. Unless you will be streaming high action, 1080p streams you won't need gigabit (even then, you probably won't). I'd be inclined to go with this one:
http://www.newegg.com/Product/Produc...82E16833127288
I've never used it personally, but I'm partial to D-Link, it has good ratings and can do wireless N if the need ever arises. It's also no more expensive than a non-wireless router with similar ratings.
Cat5 from PC to Router to PS3. Simple and easy. Since the PS3 has wireless G built-in, you could just run the cable from the PC to the router and use wireless to the PS3. You will not, however, get good results streaming HD media using the PS3's built-in wireless adapter. There's just not enough bandwidth in the Wireless G spectrum. But if you want to avoid headaches, just Cat 5 all the way if you can.
Also, incompatible media files are always something to be aware of when it comes to streaming video. The PS3 will not accept .mkv files and will flake out on any .mp4 that was created using QuickTime. That's where the transcoding comes in. If you're just one guy with a PC and one TV, it will work smoothly with just about any modern PC. However, if you need to run multiple streams (more than one tv, simultaneously) or the PC needs to be in use for anything short of browsing the internet, then you could have more problems. I prefer to just remux my files to compatible formats, but that can have a pretty steep learning curve.