Det låter bra, ta en titt på ett liknande fall:
http://www.wn.se/t1042226.html
Glesys är generellt ett bra val, men det finns fler, tex:
www.citycloud.se
Jag rekommenderar dig att köra Debian, samt det finns många howto hur du ska göra på Debian. Att sätta upp det hela är faktiskt enklare än man tror. Om du ska köra databas på vps:en bör du tänka på att ha rejält med minne redan från början, men naturligvis kan man alltid uppgradera senare, men när du jämför olika vps leventörer bör du även jämföra priser med 1G och uppåt eftersom du säkert för eller senare måste uppgradera.