I don't know what you mean by "substitutability a la planar algebras," since I don't know anything about planar algebras, but here's my take. Knot diagrams can be interpreted as (representatives of) certain morphisms in the category $\text{Tang}$ of tangles, which can be succinctly described as the free braided monoidal category with duals on a self-dual unframed object. More precisely, this category has a distinguished set of generators given by all of the structure I just described (the braiding, the self-duality, etc.), and a knot diagram is a description of a certain type of morphism $0 \to 0$ in terms of these generators.

they are relation-like, relating segments of a link to each other.

The category of tangles is analogous in some ways to the category $\text{Rel}$ of sets and relations; in particular, they are both dagger categories.

On the third hand, the Reidemeister moves seem like a set of formulas in a model-theoretic interpretation (of a "theory" of knot isotopy into a "theory" of graphs.)

I admit I don't really know what you mean by this either. The Reidemeister moves describe certain relations that hold in $\text{Tang}$ between the generators.

Finally, there's the standard trick of calculating invariants by recursively applying certain skein relations to get to the unknot.

By the universal property of $\text{Tang}$, any self-dual unframed object in a braided monoidal category gives rise to a braided monoidal functor from $\text{Tang}$, which imposes some relations (such as skein relations) on the generators.

From my perspective the situation is at heart no more complicated than describing a group by generators and relations and naming elements of that group in terms of products of the generators (provided that you've accepted Reidemeister's theorem).