There can't be a straight answer to your question. You need solid numbers to benchmark against.
For example:
Given 3 concurrent visitors browsing and 1 customer placing an order, the average load time for a category page should be 0.8 seconds or faster.
Also, you should specify the Magento and the PHP version you will be using in addition to the MySQL server variant (Mysql? Percona? MariaDB?) and version.
That said, I think you should be fine using a medium dedicated (VM) server if the stack configuration is tuned well. You might want to consider using a PHP side full page cache though.