Edit: Actually for much better presentation and description of the type of information I talk about below see this library and this article.
But I would also imagine most images libraries would have lanczos available. I have used FreeImage, which seems to have a mostly-decent C# wrapper.
Quality is largely about the interpolation algorithm used, and the ratio of the resizing. In Paint.net and Photoshop they have a dropdown to select them. Each algorithm will vary in what it does best (downsizing, upsizing, resizing by a integer ratio...) and each will have different speeds. Also Paint.net has the "Best Quality" option which will tell you what it decides to use (although I'm not sure what super sampling refers to...), doing manually do that with a few of your images and target size to see what it uses might help you choose a quicker algorithm.
@SamPlusPlus's answer uses HighQualityBilinear which IIRC is great for resizing and adding a small amount of blur (so sharp lines would be anti-aliased by the algorithm) Where Bicubic will retain more sharpness of lines. So out of these two, bilinear is generally better for upsizing, and bicubic is generally better for downsizing.
I believe the Lanczos algorithm is one of the best all-around algorithms (does very good at any amount of upsizing or downsizing) but is also one of the slower ones. I'd highly suggest it if you were reducing images by say 7% (the ratio 100:93 is difficult to reduce).
If you're doing 50%, 25%, 200%, etc all the algorithms will be very similar results, with speed being the only difference.
I would suggest looking for a library that has Lanczos resizing algorithm if the size of either the input or the output files is going to vary much, due to it being very good no matter the type of resizing, and because you did not mention speed being important, only quality. I have not used such a library in C#, so I do not have any direct recommendations.