We have customers running oscommerce on VPS servers. As for the size server you need it would depend on how busy your sites are. I always suggest to customers to go as big as their budget will allow. One thing you do not want to do is shortchange your server. There are many VPS providers, you just have to do your homework and research to find one that fits your budget and has what you need in terms of service, and support.