A lot of the customers we manage use software-based firewalls (typically iptables managed by Bastille for Linux with extensions we add) with great success.
We've found that on today's hardware (real Pentium's; I cannot speak for Celeron's), you can easily have 5,000 or so rules within the firewall and the performance of the services on the box are not impacted to anything noticable.
There is hosting companies out there that can and will put your Windows based server behind a gateway firewall. It will not give you a 100% protection against everything but it will give you a good amount of protection. I personally prefer to build gateway firewalls with OpenBSD and PF and then create a nice light ruleset utilizing <table>'s and $lists along with other macro's. This makes the firewall VERY VERY fast and can take quite a hit DoS wise and shake it off if you tune it right.
We had one little p2 400mhz with 256mb 4gb SCSI shake off a 32mbs DoS for 3 days without a problem.