Известно, что первый вызов WCF сервиса занимает несколько больше времени, чем остальные. Это связано с тем, что в момент первого вызова происходит инициализация стека канала, security и т.п. Но обычно речь идет о задержке порядка 1-3 секунд, а никак не 20 секунд. Если проблема тут в WCF, то можно попробовать облегчить binding, убрав неиспользуемые настройки безопасности для канала. Для wsHttpBinding:

<bindings>
    <wsHttpBinding>
        <binding name="Binding1">
            <security mode="None">
                <transport clientCredentialType="None" />
                <message establishSecurityContext="false" />
            </security>
        </binding>
    </wsHttpBinding>
</bindings>

Для netTcpBinding:

<bindings>
  <netTcpBinding>
    <binding name="PortSharingBinding" portSharingEnabled="true">
      <security mode="None" />
    </binding>
  </netTcpBinding>
</bindings>

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

Можно попробовать посмотреть логи WCF, чтобы выяснить, на какую операцию уходит больше времени. Для этого можно использовать стандартный инструмент Service Trace Viewer Tool (SvcTraceViewer.exe). В документации сказано, что уровень логгера Information может быть использован для замеров производительности.