Обычная медленная работа сервера при запуске - это ускорение пула приложений IIS, но в своем вопросе вы указали, что, хотя первый запрос составлял 900 мс, только 16 мс было потрачено на запрос сервера в соответствии с фидлером. Если это правда, это говорит о том, что что-то происходит на стороне клиента.
Одна из возможностей заключается в том, что некоторые клиентские приложения, которые сериализуют объекты, генерируют и компилируют код сериализации для этих типов данных во время выполнения, что может привести к снижению производительности при запуске
http://msdn.microsoft.com/en-us/library/aa751883.aspx
http://msdn.microsoft.com/en-us/library/ms733901.aspx
Я не знаком с протобуфами, но компиляция кода сериализации - компромисс, который делает первый вызов значительно медленнее, но делает последующие вызовы быстрее.
Не уверен, что это ваша первоначальная стоимость, но это возможно.