Need Advice on How to Clean Up Infected PC

I encountered a pop-up window informing me that my computer was infected and it would “help” in removing the malware. I rushed to download it without thinking twice. I now regret this as I ended up having a severely infected PC with spyware. What is the best way to remove the spyware without having to reformat my PC?And how do I avoid this in the future?What anti-spyware would you recommend?Thanks
