basrach

Квантировать. Также как и делает операционная система с процессами. Процессов много, а центральный процессор один. ОС просто даёт маленький интервал времени каждому процессу, все выполняются по очереди и все счастливы.
Самый простой способ - разбить весь массив на пачки по 100 (10, 1000), между обработкой пачки делать тупо Thread.Sleep(300 или меньше), давая тем самым обработать запросы серверу. Параметры подобрать экспериментально.

DECLARE @teachers TABLE ([LastName] NVARCHAR(255) NOT NULL);
INSERT INTO @teachers
VALUES
(N'Холстинин'),
(N'Пирожков'),
(N'Пугачева'),
(N'Цой');

DECLARE @vowels TABLE ([Letter] NCHAR(1) NOT NULL);
INSERT INTO @vowels VALUES
(N'а'),
(N'о'),
(N'и'),
(N'е'),
(N'ё'),
(N'э'),
(N'ы'),
(N'у'),
(N'ю'),
(N'я');

SELECT [t].[LastName]
FROM @teachers [t]
CROSS JOIN @vowels [v]
GROUP BY [t].[LastName]
HAVING SUM(LEN([t].[LastName]) - LEN(REPLACE([t].[LastName], [v].[Letter], ''))) > 3;

Используйте DateTime?, с вопросительным знаком. Это как обычный DateTime, только он может иметь значение NULL. Он специально создан для таких случаев.

Когда EF достает данные, можно сказать чтобы он даты считал в UTC.
Посмотрите здесь и здесь.
Ну дальше либо new DateTime(01.02.2018).ToUniversalTime(), либо new DateTime(31.01.2018, DateTimeKind.Utc)

В любом случае нужно хранить у себя. Это даже не подлежит обсуждению. Чтобы ваш сервис не перестал работать, образно говоря, из-за того, что где-нибудь на другом конце мира уборщица шваброй задела провод. Но как вы правильно заметили, встает другая проблема - актуальность данных. А её решить достаточно просто. Забирайте данные из стороннего api периодически и обновляйте данные у себя в базе. Как часто это делать, и каким образом, полностью заменять локальные данные/подтягивать только обновления и т.д.? - Зависит от объема данных, природы этих данных и пр. В случае списка городов наверное можно автоматический апдейт делать раз в месяц или даже раз в квартал, или даже раз год. Не так часто появляются/исчезают/переименовываются города. И по необходимости можно запустить обновление вручную.
Если вы не последуете этому совету и решите запуститься без локальной копии. То в скором времени вам всё равно придется переделывать. Потому что в реальном мире сети рвутся, сервера падают, фаерволы режут трафик, а сервисы внезапно перестают отвечать на запросы.

Как вариант. Можно привести сначала строки к какому-то "нормализованному виду". Например, удалить всё кроме букв, удалить места с наиболее вероятными ошибками (буквы а, о), заменить всю кириллицу на латиницу и т.п. и затем положить это всё в в словарь, где каждому такому "хэшу" будет соответствовать 5-10 похожих наименований. При добавлении новой записи сначала вычислять "хэш", затем по соответствующим ему 5-10-15ти записям пройтись нормальной функцией поиска соответствия. Идея в том, чтобы не шерстить все 70к каждый раз, более 90% из них очевидно даже близко не похожи. Собственно нужно просто подобрать способ как отфильтровать эти 90+% заранее.

Компилятор говорит, что не может понять какой параметр типа (generic type parameter) нужно подставить вместо TContext в метод SetInitializer и просит этот TContext указать явно. Но указывать явно на самом деле не нужно, нужно сделать так, чтобы StaticDbInitializer реализовывал интерфейс IDatabaseInitializer где контекст вероятно должен также быть унаследован от какого-нибудь DataContext-а.
Первый шаг, который нужно предпринять - записать объявление класса как:
public class StaticDbInitializer : IDatabaseInitializer
{
....
Где MyContext - класс, который представляет... некий контекст

PS Локализованная IDE - зло