well, clean, sharp and low light don't get along very well together. In low light, even with a fast lens, you are typically at high iso, wide open aperture and slower shutter speeds. This means that you will have a more shallow depth of field (less in focus), more noise, and possible motion blur or camera shake to contend with. IS helps with everything but motion blur, so it is nice to have. A fast lens helps with everything except obviously getting more depth of field. Both are nice.
However, a good, fast, IS lens is going to be quite expensive - starting around $1,000.
Mark above is right, you need to be thinking about what focal length and other characteristics you are looking for first and then look at the options that fit your criteria.