Dipende dalla lunghezza della stringa data in input.
Effettivamente se parliamo di parole, ovvero stringhe che difficilmente sono superiori a 10 caratteri di lunghezza, è più veloce iterare su ogni singolo elemento.
Se però si volessere contare le occorrenze di ogni singola lettera su di una stringa molto lunga (es: un testo) risulta più performante utilizzare set() e ''.count().
Un po' di benchmark:

codice:
# -*- coding: latin1 -*-

consonanti = 'bcdfghjklmnpqrstvwxyz'
vocali = 'aeiouàèìòù'

def conta1(parola):
    cons = 0
    vocs = 0
    parola = parola.lower()
    lettere = set(parola)
    for lettera in lettere:
        if lettera in consonanti:
            cons += parola.count(lettera)
        elif lettera in vocali:
            vocs += parola.count(lettera)
        else:
            # carattere estraneo (!$%& ecc...)
            pass
    return cons, vocs

def conta2(parola):
    cons = 0
    vocs = 0
    for x in parola:
        if x in consonanti:
            cons +=1
        elif x in vocali:
            vocs += 1
    return cons, vocs

import timeit
print timeit.Timer('conta1("difficile")', 'from __main__ import conta1').timeit(1000)
print timeit.Timer('conta2("difficile")', 'from __main__ import conta2').timeit(1000)
print timeit.Timer('conta1("difficile" * 1000)', 'from __main__ import conta1').timeit(1000)
print timeit.Timer('conta2("difficile" * 1000)', 'from __main__ import conta2').timeit(1000)
A me ritorna:

0.0187870246079 secondi utilizzando set() su stringa corta
0.00785407083861 secondi utilizzando for su stringa corta
1.42217516472 secondi utilizzando set() su stringa lunga
5.30397271162 secondi utilizzando for su stringa lunga

Cmq sicuramente esisteranno approcci migliori, sia che utilizzare set() che iterare su tutta la stringa.