В похожей известной мне ситуации заказчик, заказав оценку стоимости у десятка различных исполнителей, получил разброс стоимости проекта от 400 тысяч до 32 млн рублей. (Заказчик в итоге отказался от проекта вообще).

Не знаю, есть ли в такой ситуации вообще какое-то единственно правильное решение, но помочь вам могут методы оценки стоимости проекта, тот же самый PERT. В двух словах:
Декомпозируйте задачи настолько, насколько это необходимо для того, чтобы их оценить хотя бы предварительно.
Выполните, исходя из имеющегося опыта, оценку сроков получившихся задач по трём точкам: оптимистическую, наиболее вероятную, пессимистическую. В этих оценках постарайтесь учесть возможные риски.
Вычислите ожидаемое время проекта на основании получившихся оценок, накиньте пару стандартных отклонений в плюс и минус: получите достаточно широкую вилку суммарного времени работы над проектом, но с высокой вероятностью включающей в себя то время, которое может получиться по факту.
Умножьте получившиеся оценки на стоимость работы вашей команды (в час/день -- какую единицу при оценке сроков использовали), таким образом получите оценку стоимости проекта сверху и снизу. Презентуйте получившуюся вилку и скоуп проекта, который лёг в её основу, заказчику. Сужайте вилку на свой страх и риск.

Если нет опыта, на основании которого можно было бы оценить масштаб работы -- лучше откажитесь от проекта.
Если не готовы выполнить такую оценку бесплатно -- лучше откажитесь от проекта.
Если скоуп проекта даже в таких приблизительных рамках очертить не получается -- лучше откажитесь от проекта.
Избегайте заключения контракта с фиксированной стоимостью, не подлежащей пересмотру, основанной на такой поверхностной оценке.

Высокая неопределённость на начальных этапах проекта -- явление нормальное, но брать на себя какие-то обязательства в таких условиях -- ваш риск. Оцените, готовы ли вы пойти на него.