Алгоритмы для эффективной нагрузки на сервис со стороны клиента?
Ответ на этот вопрос можно получить либо экспериментально либо изучив серверную реализацию (в конечном счете тоже экспериментально).

У тебя 2 основных узких 'горла' - скорость подготовки ответа сервером (процессор и диск) и скорость сетевого соединения до него... ну а медленный клиент можно распараллелить несколькими машинами (и соответственно провайдерами если проблема в сети на стороне клиента).

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

В дополнении к скорости сетевого подключения есть скорость ответа (пинг), но при множественных подключениях клиента к серверу, его влияние на результат почти исчезает.

Ну и вишенка на торте, транспортный уровень может внести корректировки, полистай статью

Если говорить про сервер и его возможность в принципе отвечать с какой то скоростью (самый частая причина лимита скорости обработки запросов) то тут все зависит от того, как подготавливается ответ, какие ресурсы на это тратятся и т.п. например тормоза могут вытекать из медленной скорости чтения диска...

С диском совсем грустно, например hdd может нелинейно уменьшать скорость ответа в зависимости от его нагрузки и еще сложнее - в зависимости от размещения данных на нем, т.е. если клиенты (или алгоритмы балансировщика на сервере) подгадают порядок считываемых данных на последовательный, то скорость чтения может быть сотни мегабайт в секунду, а если запросы будут случайными, то считанные мегабайты. Т.е. в следствии чего возможна ситуация когда один клиент, последовательно запрашивающий данные в определенном порядке будет отрабатывать запросы значительно быстрее (на порядок или два) чем несколько параллельных и наоборот, если сервер будет специально притормаживать 'плохие' запросы, организовывая правильно доступ к диску то много параллельных клиентов лучше одного (в этой схеме лучше сделать один клиент который сразу делает все возможные запросы, паралельно, и ждет ответы).

Ну и нагрузка на процессор, если реализация однопоточная (асинхронная реализация сильно усложнит подсчет) то скорость ответа будет линейно зависеть от времени обработки одного и нагрузки на процессор (проще замерить сколько клиентов дадут 100% нагрузку). Но вот многопоточные реализации могут давать неожиданные ухудшения характеристики, т.е. 10 потоков могут не дать 10-кратное увеличение скорости, и с величением потоков будет много ресурсов уходить на поддержание этой работы (кажется теория вообще говорит о квадратном корне из количества потоков), и это еще про кеш процессора речи не идет, так как в зависимости от того, влезает ли алгоритм обработки (нужная ему память) в него или нет тоже можно получить кучу странностей, например 1-2 потока будут давать быструю скорость, но добавив третий, даже не нагрузив весь процессор, можно получить значительное понижение производительности, так как данные трех потоков не влезают в кеш. Кстати оперативная память хоть и называется Random Access memory но может давать разную производительность в зависимости от характера нагрузки (особенно это видно по вычислениям на GPU) что тоже не лучшим образом влияет на многопоточный результат.

т.е. может так получиться что аренда большого количества слабых блейдов будет эффективнее небольшого количества мощных серверов
Скорее всего прямой формулы не существует. Есть сравниительные подходы. Тоесть к примеру вы знаете уже такую конфигурацию которая "держит" 10 млн запросов. Вот смотрите как она реализована. Скорее всего это не один сервис а целый грид сервисов которые географически разбалансированы так чтобы каждая нода брала на себя часть нагрузки.

Почему в подобного рода задачах нельзя создать формулу? Ну формула - это скорее всего иммитационное моделирование всех уровней вашей системы в том числе сетевого стека и пользователей. По сложности эта модель близка к разработке самой системы. Поэтому я думаю что такой подход вам не нужен. Да и мало кому вообще нужен. Разве что атомный взрыв так моделируют.