I think any shared host geared towards the quality end of the spectrum (i.e. non-overselling hosts) would be the goal at this point. I don't see any need to jump immediately to a VPS unless there is any custom code involved (something that would be more safe in a more secure VPS environment).
As you're using xcart the obvious requirements will be in play:
Link to details
Technical requirements for hosting packages
Web server must have support for PHP version 4.0.6 or higher (X-Cart is also compatible with PHP 5). The configuration file php.ini must contain the following settings:
a. safe_mode must be disabled
b. file_uploads must be enabled
c. [PHP 5] register_long_arrays must be enabled
d. the functions "exec", "popen", "pclose" and "ini_set" should not be included in the disabled functions list
a. EXPAT PHP extension is installed
b. libCURL PHP extension and/or an HTTPS module (like Net:SLeay perl module, CURL executable, OpenSSL executable) is installed
c. Perl is required for Net:SLeay perl module
d. GDLib version 2.0 or better (required for X-Magnifier module)
The web server must have support for MySQL databases. X-Cart is compatible with any MySQL version from 3.23 to 5.0.18 inclusive. Clients must be granted the ability to choose between MySQL v 4.x or v 5.x at least.
• Shared SSL certificate.
• Ability to install any SSL certificates chosen by client.
• Clients data protection. No access for users from other hosting accounts.
1. Outgoing connections to 80 and 443 ports must be enabled.
2. Loop-back connections must be enabled.
3. There should be no restrictions on memory and processor time usage for PHP. If such restrictions exist they must be adjusted or disabled upon clients requests.
The majority of hosts out there using a LAMP configuration (linux, apache, mysql, php) should be sufficient.