Most hosts capable of running Drupal should be able to run Commerce Kickstart. A PHP memory limit of greater than 128M is required.

These hosts have proven experience with running Commerce Kickstart:

Commerce Guys: The software vendor that created and maintains Drupal Commerce and Commerce Kickstart - offers Platform.sh, a Platform-as-a-Service for running Commerce sites: https://platform.sh

Pantheon: Cloud hosting for Drupal, features a 1-click installer for Commerce Kickstart 2.x.

Acquia: Enterprise-grade cloud hosting for Drupal.