You should consider their:
Experience in the industry
Verifiable reputation on independent websites
Licensing and insurance
Transparency about costs
Care and expertise in answering your questions.
Fleet condition over the number of vehicles it contains