i don't know about soldat requirements, but for css atleast, you wouldn't want to run it off anything but a dedicated server or at the very least a high end vps geared towards it (in other words, a very minimal number of vps accounts with a high amount of guaranteed ram - not a general vps account which is more geared towards web hosting). If Soldat can run stable on 256mb ram max (fitting under your $100 budget) and uses minimal cpu usage then you might be able to run it.
Anyway, you're best bet is to probably talk to Net Logistics about VPS's, else you might want to consider spending a little more and getting a lower end dedicated server (again not sure on soldat requirements and what server specs you'll need).