A lot of VPS providers probably won't go up to providing 2GB guaranteed RAM, I don't think. DA shouldn't be a problem, it is fairly cheap to license with a VPS or Dedicated from your provider. I think your best off with a dedicated to be honest, up the budget to $150 and you may be able to get something.
Staminus will do an Intel Core 2 Duo 1.86 with 160GB hard drive and 1GB ram for $149 / Month. That includes 2000GB of bandwidth. For another $20 on top ($169 / Month) you can up that to 2GB RAM and have a nice system.
It may be worth it spending a little bit more to get a quality dedicated server, for example at Staminus - they've always been great for me and they have GREAT support! Also remember it's probably best to purchase something you can expand into, not just on your border line of resources