Hardware Firewall Vs. Software Firewall (IP Tables, RHEL)
Solution 1:
Hardware firewalls are running software too, the only real difference is that the device is purpose built and dedicated to the task. Software firewalls on servers can be just as secure as hardware firewalls when properly configured (note that hardware firewalls are generally 'easier' to get to that level, and software firewalls are 'easier' to screw up).
If you're running outdated software, there's likely a known vulnerability. While your server might be susceptible to this attack vector, stating that it is unprotected is inflammatory, misleading, or a boldface lie (depends on what exactly they said and how they meant it). You should update the software and patch any known vulnerabilities regardless of the probability of exploitation.
Stating that IPTables is ineffective is misleading at best. Though again, if the one rule is allow everything from all to all then yeah, it wouldn't be doing anything at all.
Side Note: all my personal servers are FreeBSD powered and use only IPFW (built-in software firewall). I have never had a problem with this setup; I also follow the security announcements and have never seen any issues with this firewall software.
At work we have security in layers; the edge firewall filters out all the obvious crap (hardware firewall); internal firewalls filter traffic down for the individual servers or location on the network (mix of mostly software and hardware firewalls).
For complex networks of any kind, security in layers is most appropriate. For simple servers like yours there may be some benefit in having a separate hardware firewall, but fairly little.
Solution 2:
Running a firewall on the protected server itself is less secure than using a separate firewall machine. It does not have to be a "hardware" firewall. Another Linux server set as a router with IPTables would work fine.
The security problem with firewalls on the protected server is that the machine may be attacked through its running services. If the attacker can get root level access, the firewall can be modified or disabled or bypassed through a kernel root-kit.
A separate firewall machine should have no services running except for SSH access and that SSH access should be limited to administration IP ranges. It should be relatively invulnerable to attack, barring bugs in the IPTables implementation or TCP stack, of course.
The firewall machine can block and log network traffic that shouldn't exist, giving you valuable early warning of cracked systems.
Solution 3:
If your traffic is low, try a small Cisco ASA unit like the 5505. It's in the $500-$700 range and definitely purpose-built. The co-lo is sorta giving you BS, but their rates for the firewall are also unreasonable.
Solution 4:
I think it also depends on performance. What a software/server based firewall does using CPU cycles, a hardware firewall can do with purpose built chips (ASICs) which leads to better performance and throughput.
Solution 5:
From your perspective the real difference between "software" (on the machine itself) and "hardware" firewalls is that in the first case the traffic is already at the machine you want to protect, so it's potentially more vulnerable if something has been overlooked or misconfigured.
A hardware firewall essentially acts as a pre-filter, which only allows specific traffic to reach and/or exit your server.
Given your use case, and assuming of course that you have proper backups, the extra expense would be very hard to justify. Personally I'd continue with what you have, although perhaps using a different hosting company.