Почему запроса MySQL на VPS выполняется на порядки дольше?
все что указано - мусор. Какие процессоры? сколько там памяти - не так важно. Какие диски? Может там magnetic? Какая конфигурация базы? 
Сравнивать надо все
Берите не самый дешевый хороший Впс и все будет хорошо, если вы в рф- можете взять Кселент