To start with ...
When talking to a host there are several questions to ask:
1- What type of server will I be hosted on?
2- What version of php is installed?
3- What version of mysql is installed?
4- Is there SSL available? What if I have my own certificate?
5- Do you use a single HTTP directory or a double HTTP and HTTPS system?
6- Is SAFE_MODE enabled?
7- Do you have any php functions disabled?
JMHO- If the person you are talking to can not answer any of those questions ... RUN!
Minimum/suggested server requirements for Zen Cart v1.2.x or v1.3.x: PHP 4.1.x or higher (PHP 4.3.3+ for optimal performance), Apache 1.3.x and MySQL 3.2x.x or higher.
For Zen Cart v2.0 and newer, Minimum PHP 5.2 and MySQL 4.1 or higher. CURL is also HIGHLY recommended.
Additionally, SSL support is very important when running an eCommerce site.