I use Avast AV and like it BUT its not the best out there but its free. Being free I keep it and i don't go into fearful places at least i try not to. I mention this because other "paid for" tend to better and may stop or correct some malware far quicker or give ntoice. I suggest you visit some of the "online scan services" from the likes Norton, Klasasky, etc.. Visit the spyware, security and virus forum and find the "sticky note" for all the web links and do various vendors online scans. Once that's done then it should be more trusty on the malware side.
Next, while I use CCleaner too, I use it at its default nothing fancy. If you play too much in the registry type cleaners they can bite you, thus I remain at default setting, unless I'm well aware of its doings. Since, you mention two different cleaners, pick one and stay with it.
I know in the past weeks, big OS updates have occured. So, you maybe feeling the effects of these though they shouldn't slow you down, but issues do arise sometimes, google for your OS what maybe said about OS updates. Also, click the "task manager" to see what being done int he backgrd., so check and verify. Alas, you may want to use HiJackthis s/w and verify what going on there.
Sorry, but you mentioned slow boot time but it may not be where the fix lies. As Already stated above look to see if any malware or added pgms(unknown to you) are in play here. Don't take anything for granted.
If all fails, you may want to use a restore point to return to a date when you know this issue wasn't present. If that corrects that and the problem returns, become aware of what has transpired.