A few things to check when choosing a new host.

• Cost
• How much disk space is available
• Are PHP and MySQL supported
• SSH available with SSH keys for scripted access
• SSL certificates for https access to website
• Can check website before changing nameservers
• Number of email accounts
• Email forwarding
• Webmail
• Domain redirection
• Check reviews on the web