These are areas I and my technicians deal with every day... unfortunately usually after a client has been infected with malware and viruses. Here's my thoughts on your questions:
Q. Can you be too safe, and do you have to break the bank to be safe?
A. Taken to the ridiculous extreme, probably yes. I know of people who are so paranoid they buy every anti-whatever program known to man and practically cripple their pc and the usefulness of it by never browsing anywhere they aren't already familiar with, refusing attachments from any email (even friends and family), refusing to go broadband because it's "always on" and so on. You get the picture.
What you and I and most people need is a reasonable balance between enjoyment of the web, safety and security.
If you are already running Spybot, Ad-Aware, Norton AV and Zone Alarm, you're already ahead of the game. My only suggestions here would be to add a good pop-up blocker (Panicware has a pretty good free one, or you could use the one that comes with Google's toolbar for example), and a spware application that is more automatic than Ad-Aware and Spybot.
The downside to SpyBot and the free version of Ad-Aware, as good as they are at what they do, is that they have no or limited active protection, and you must remember to manually update them and manually run them (note that the brand-new 1.4 version of SpyBot has a scheduler which will allow you to schedule updates and scans).
If you want to spend just a little money on a spyware program, I would suggest you take a look at Counterspy, from Sunbelt Software. You can download a fully functional trial version for 30 days. It uses the same engine as Microsoft's Antiwpyware Beta, but goes further and adds it's own expanded definitions and options. As of this writing, we don't know what Microsoft's intentions are with their Beta program, which expires on 31 July, although we're all hoping that they keep it free.
The caveat noted in CNET that all these programs might not catch the newest threats is true. There is no, nor will there ever be, a 100% guarantee from any one, or even a combination, of programs. The antispyware and antivirus game is a constant see-saw battle between The Force and the Dark Side of the Internet.
The common key factor to an effective security solution is prevention. It is much easier to keep the bad guys out than to try to find them and chase them down after they've already gotten in. That's where your firewall, antivirus and (mostly paid) active antispyware applications shine. Keep them up to date and run the antispyware and antivirus apps regularly (I recommend late at night so they're done by the time you get up and back to your pc).
The Anti pop-up software, although it does add some additional protection, is more of an anti-annoyance tool.
Make a backup of your critical data and settings to some external media (CD/DVD, ZIP drive, Flash Drive, External USB disk, etc.) This is your disaster insurance in case of disk crash or other unrecoverable error.
The last leg of your security suite whish we haven't mentioned, is to keep your operating system fully patched and up to date. If you have Windows 2000 or XP, turn on automatic updates from Microsoft. Whether you choose to automatically download and apply, or download and review yourself before instlling, is up to you and your preference.
Q. Why do some programs exist?
A. While your observation is correct that many utility type programs, such as the CCleaner that you mentioned, do the same thing that you can do manually, they do it more automatically, and in some cases, better than the utilities embedded in Windows. One-click fixup, and free besides... not a bad thing.
Almost every utility program offered, whether free or paid, was designed to either address a shortfall or oversight in Windows, do what Windows does, but better, or to simply make what Windows can do easier.
Even Windows itself has utilities that are little known or only marginally documented. As an example, back in the Windows 9x/ME days, you would find many contributors to these forums recommending the use of disk cleanup, scandisk and defrag on a regular basis to keep a system running in top form. Most people ran each one manually and individually, never knowing that Microsoft included a utility called Tuneup that would do all three, and do it automatically, on a schedule the user could choose!
As for wasting MB on utilities, only you can decide how you want to allocate space on your hard disk. In these days of 250Gb hard disks and larger, it's kind of a moot point, but if you're constrained by disk space for any reason, then it's up to you to decide whether a utility is worth the space or not. I might point out that most utilities such as CCleaner, take up very little space (the CCleaner installer is less than 500Kb for example) and many are single run utilities, which means they're not loaded automatically nor do they sit in the background consuming memory (a much more critical factor than hard disk space) when they're not running.
Okay, back to your first question, and to sum up in a much shorter form, here's a good formula for software-based PC Security (listed in order of importance):
1. Keep your Operating System fully patched and up to date. If you do nothing else, do this.
2. Buy and keep current a good commercial Antivirus program. If money is a factor, use one of the free AV programs, such as Avast, or AVG antivirus.
3. Make and keep current, a backup of your critical settings and data to any external media of your choice.
4. Use a software firewall, such as Zone Alarm, that monitors traffic IN and OUT. Window XP firewall, though much better than nothing, only monitors INBOUND traffic.
5. Use Anti-Spyware software, keep it/them up to date and run regularly.
6. Use a pop-up blocker.
These, along with a reasonable dose of common sense surfing and email use, will go a long way to keep you from the "I was a victim" crowd.
Good job and good luck!