Я бы пошел с первым подходом.Но вам действительно нужно хранить их в словаре?Вы уже имеете их в коллекции, верно?Вы можете использовать LINQ для фильтрации самой коллекции.
var cityFiltered = from p in AnonymousClientList where p.city == 'London' select p;
и т. д. и создать свою отфильтрованную коллекцию.
====== ОБНОВЛЕНИЕ ======
Вот обновленный запрос для фильтрации по городу:
var filtered = (from c in clients where c.Value.city=="London" select c).ToDictionary(x => x.Key, x => x.Value);
Если вы видите, первая часть в основном возвращает вам логическое значение для вашего условия, а не объект словаря, который вам нужен.Используя метод ToDictionary, вы преобразуете обратно в словарь.Итак, теперь после выполнения LINQ у вас будет весь AnonymousClient с городом, установленным в Лондон.