What is the best method for stick-free cooking of bacon in a stainless steel pan? I recently made the switch from the non-stick pans to stainless steel. If it helps, I also have a natural gas stove-top.

I began cooking bacon and did not add any oil to the pan as I figured the bacon grease would be enough to prevent any sticking. Knowing sticking is a problem with stainless, I started out with a lower temperature. But as the bacon started to cook, more and more 'residue' built up on the bottom of the pan. I tried to frequently move the bacon around, but between that and the low temperature, it was taking forever to cook.

I should also add that as the bacon was close to being finished cooking, there was a good amount of grease in the pan, so I threw in some thinly sliced potatoes, onion, and pierogies. Have done this before in the non-stick without any issues. What ended up happening in the stainless was that the residue began to build up more and more, and it was tough to get the food to cook. I managed to get the food to turn out pretty good, but I was left with a thick layer of stuck on food. It was at the point where the food was cooked just enough to my liking, but if it needed more cooking the residue would have burnt and probably ruined the food.

So, I know throwing all that other stuff in the pan didn't do me any favours, but even still if I had just cooked bacon there would have been stuck on food. What could I have done to avoid that?
First of all, it is difficult to get right. Don't be disappointed if you need some time to learn how to do it well. 

As for your method, there are two things in your description you can improve on. One is the fat. You need a lot of fat to fry in a stainless steel pan. The bacon grease is unreliable even if you have the rest of the process perfected, and makes it much more harder at the beginning. So adding fat will be a good place to start. And you probably need more than you think - at least 3 mm thick, better 5 (assuming we are talking thin slices of bacon and not cubes or slabs). 

The other thing is that you lowered the temperature. This was the wrong thing to do. You want a heating rate at which your bacon's proteins start shriveling up as soon as they hit the fat, as opposed to slowly gumming up against the bottom. This tends to be higher than most people first try, and certainly higher than the heat you can use with a nonstick. Sadly, you can also overshoot and have the bacon burn and stick at the same time - that's one of the major difficulties with getting it right, learning how to recognize if you are in the proper range of heat - but if in doubt, you probably have to go up rather than down. And preheat for a good long time before laying the first strip in. 

Another thing to consider is the bacon itself. Some brands are sweetened, and the sugars stick like crazy. They also burn at temperatures where the meat does just right. So, look at the ingredients, and if you notice any kind of sugar - could be fructose, corn syrup, maple syrup, or something else - choose another brand. Also get something which is packaged dry, these which are wet enough to have something marinade-like in the package will stick more.