Насколько тяжело работать с большой MySQL базой?
1. примерно 700 мегабайт
2. зависит от индексов, организации. Если правильно проставите индексы, то проблем не будет и запросы будут обрабатываться быстро. У меня есть один сайтик с 60млн записей в одной таблице - все норм. 
3. Желательно взять с ssd, но такие стоят дороже.
1) Сколько места будет занимать база с 1 млн подобных записей? В текущих реалиях - незначительное. Грубая верхняя граница - 10Гб (плюс-минус пара петабайт).Насколько тяжёлые будут запросы к выборке из такой большой базы?Зависит от запросов.Если база увеличится до 10 млн, то и длительность/тяжесть запросов пропорционально в 10 раз увеличится?Прямой корреляции между размером таблицы и скоростью выполнения запросов нет, движущихся частей в этом процессе довольно много - это и индексы и структура самих запросов.На какие параметры стоит обратить внимание при выборе хостинга/vps/vds под такую базу?Для сферической базы в вакууме, с которой будет работать сферическое приложение в вакууме берите тот сферический VDS в вакууме, на который у вас хватает денег. Если он не будет справляться со сферической нагрузкой в вакууме, берите VDS мощнее. Live - Die - Repeat.
P.S.Насколько тяжело работать с большой MySQL базой?К вечеру начинает лапы ломить и хвост отваливается, но в целом - терпимо.