Linode offers both $5/mo and $10/mo plans (and prohibits only child porn, non-consent, and bestiality, which they'd have to be really churlish to lump furry with), though admittedly the 25GB or storage on the $5 one would be a constraint. Digitalocean probably has something similar. But the real barrier there is likely the learning curve.
Malware scans are approximately worthless, and from the sounds of it Lunarpages' one produces loads of false positives. It's not problem-solving, it's waving a divining rod.
Re HostGator, it's not immediately clear what their "cloud" offering is, but SMF is an old-style single-machine app, which makes me slightly anxious. Though as long as the system presents (1) a single, shared MySQL database, and (2) a shared data directory, I think SMF should work. It, uh, would be good to see if you can test it before buying. They appear to have a 45-day money-back guarantee, and IIRC part of why HostGator were well-regarded back in the day was because they were really good at fulfilling that guarantee (and it was longer than most).
4GB should be plenty.