1) To run a dedicated game server, what you need to do is install the server for that particular game. For example, I used to run my own Counter-Strike server. Since that's a Half-Life mod, I went to Valve Software's website and found Half-Life Dedicated Server for Linux. At that point in time, Valve had bought the rights to CS from its original makers so it was included in the installer, but if I wanted to do it for a third-party mod like Natural Selection which ISN'T supported by Valve, then I would have to download a special file from the makers of the mod and follow their instructions to install it.
2) It's MUCH better to run a dedicated server in Linux than Windows. First of all, Linux has ROCK-SOLID stability - my dedicated server ran literally forever without a hiccup, and it would probably still be running great if I hadn't decided to shut it down (I stopped playing CS, so I decided why waste the money on electricity if I'm not the one using the server?). Unix systems make GREAT servers.
Second of all, I don't know what game you're planning on playing, but if it's Half-Life (or a Half-Life mod, or HL2 or one of its mods) there's a SWEET option you can add to the server program's start-up command called "pingboost" which has 3 different modes - the first reduces latency by 10ms, the second does the same thing but using a different method which supposedly works better for some computers, and the third gives everyone a HUGE drop in latency by processing a frame every time a packet arrives. I had a 400mHz system with 192MB RAM and a pretty old, crappy network card for my server, and even with 10-12 people on there no one complained about having lag.
3) The best place to look for the dedicated server program is on the website of the game the server will be for. If you mean "where's a good place to find dedicated servers for a whole bunch of different games" then I don't know - you might want to try the Half-Life server, though, since it has Half-Life, Counter-Strike, DOD, Opposing Force, and others (and you can also install third-party mods like Natural Selection, Action Half-Life, or Zombie Panic).