To ground the problem with a concrete example, this image shows several different possible real game interactions:



The grid represents the map. Each square is a node, which is used for broadphase collision detection. Entities may not be larger than a single node, so an entity only needs to check against the entities in at most 4 nodes.

The types of "hittable" entities shown on the map are:
Enemy units (red A & B)
Player unit (green C)
Player hovercraft (green D)
Water (blue squares)
Destructible obstacle (gray block)
Indestructible obstacle (black blocks)

Also show are two projectiles. Projectiles cannot be hit (they don't track their node), they can only hit other objects.

There are two primary types of interaction that can occur: Movement & Damage

Examples:
D can move through water.
B cannot move through water.
Nothing can move through the indestructible obstacles.
Nothing can move through the destructible obstacle.
Projectiles damage the destructible obstacle.
Player projectiles can move through player units.
Enemy projectiles can damage player units.

I'm still going back and forth on how to handle this. The various solutions I've started down solve one scenario, but seem to be inefficient or hackish at solving another.