Поиск будет быстрее в dict и set, потому что это хэш-таблицы, доступ к элементу которых выполняется за O(1). Для list и tuple поиск будет выполняться в среднем за O(n).
Исключение работает только для очень маленьких списков длиной до 5 элементов. В этом случае интерпретатору будет быстрей пробежаться по списку, чем считать хеш.
В Python 2 методы словаря keys, values, items возвращают список. Тоесть перед итерацией по словарю (или сету) интерпретатор сначала создает новый список, что занимает дополнительное время и память, но после создания это уже обыкновенный список. Тоесть в Python 2 итерация по словарям и сетам выполняется дольше, за счет создания нового списка и копирования в него элементов.
В Python 3 эти методы создают объект-представление. Это определенно происходит быстрее чем создание нового списка в Python2. Но итерирование по такому представлению должно происходить немного дольше, чем по списку из-за того что данные в словарях хранятся разреженно (редко, негусто). В подтверждение вышесказанного (Python 3):
>>> l = list(range(1000000))
>>> d = dict.fromkeys(l)
>>> s = set(l)
>>> def iter_list():
... for i in l:
... pass
...
>>> def iter_dict():
... for i in d:
... pass
...
>>> def iter_set():
... for i in s:
... pass
...
>>> timeit.timeit(iter_list, number=1000)
6.727667486004066
>>> timeit.timeit(iter_dict, number=1000)
9.293120226997416
>>> timeit.timeit(iter_set, number=1000)
8.627948219014797@python_job_interview