How do I set up a media server in Linux which streams video over the internet?

Is it easy to do this? I want a server that will actually encode video in real time to allow it to stream over sometimes slow or unreliable networks. Basically, I want a server that works on the internet.

I have a directory with a bunch of video files, and want to make this accessible to myself remotely.

For other situations, I found great and useful software (such as the PS3 media server). I'd like to find something equally as useful for streaming video over the internet.