Is it possible to create a promotion with the logic: Buy 3 of a category, select 3 from another category for free? I've tried to get this to work, but there seems to be no way to limit the promotion to only trigger when 3 of the category are added.

You're right... that is complex ;)

As far as I'm aware it is not possible, and would require a custom dev quote.

The closest you could get using existing functionality would be to automatically add specific free products to the cart if 3 of a category were already in the cart. The part that is not possible (as far as I'm aware) is to give customers the choice of which free items they want.

Cheers