Hmm, you're right... that one is actually quite hard to do in a Python-ish way. There is a one liner, just for the record, but it's absolutely horrific code because it redundantly re-evaluates the same conditions over and over:

    g = {fn(x): [y for y in foo if f(y)==f(x)] for x in foo}

As you said, you'd have to use a for loop. I think sometimes people are unnecessarily afraid of for loops in Python (not everything has to fit on one line!) but this is a case it's a pity to take up so many lines. Or, back to square one, probably this is a case it's best just to use itertools groupby (after a sort) after all.