When you resize a bitmap image, the program doing the resize uses either Interpolation or fractals to rezise it. So what you want to look for in a program is the best process for your image.
With interpolation, the most common methods are nearest neighbor, bilinear or bicubic (linear, smoother or sharper). Using nearest neighbor, the program reads pixel by pixel of your file and assumes what colors are close to what and uses that to resize it. This process works well for GIF files and/or files with a lot of solid colors where you want to preserve hard edges. In the bilinear process, it uses a criss cross pattern to enlarge or reduce the file, this particular process is not commonly used anymore because bicubic works best with most pictures. In the bicubic process, the program uses complicated processes to try to expand or contract the pixels for example if you have a yellow square and you are resizing it to 125%, it will figure out how to expand it to keep the constrain portions and not look so blurry. While using bicubic, you want to use smoother for enlargements and sharper for reductions. The only problem with these processes is that you can only resize an image without much loss from 1/4 to 4 times its size.
So with the evolution of technology the fractal resize process makes it possible to resize something from 1/32 to 8 times the original size.
I'm not aware of any freeware software that can do this.
Adobe Photoshop has built in the interpolation process and there is a plug-in available from on one that can do the fractal process.
Another thing you might want to consider is printing the file and scanning it at a very high dpi (like 1200 or higher) that way when you resize it you adjust the dpi accordingly, for example, if you are doubling its size, change the resolution to 600 dpi.