I'm hoping to (prove that one cannot) find an infinite first-order $\mathcal{M}$ that is:
Any such model would only have arbitrarily large, finite, pairs of tuples $(a_i)_{i<n}$ and $(b_i)_{i\subseteq n}$ for any formula witnessing the IP.
Consider the universal theory of "disjoint unions of boolean algebras", that is, a model of the theory is given by a set $I$ and a boolean algebra $B_i$ for every $i \in I$ and an embedding of structures is an embedding $I \hookrightarrow J$ of sets together with an embedding $B_i \hookrightarrow B_j$ of boolean algebras. Thus it has two sorts $X$ and $I$ together with a surjective map $X \to I$ such that each fiber carries the structure of a boolean algebra with no relation between the fibers.
There is a model $A$ of this theory with the property that $I$ is the set of natural numbers and each $B_i$ is a boolean algebra of size $2^i$; the $B_i$, and hence $A$, are uniquely determined up to isomorphism.
In this structure the set $I$ is stably embedded and essentially just an infinite set with some named elements. Namely in a saturated model each $B_i$ is either finite or else a saturated atomless boolean algebra, so if the fibers above $i,j \in I$ are both infinite then the $B_i$ and $B_j$ are isomorphic, so $i$ and $j$ are conjugate by an automorphism of the whole structure.
To finish we must only note:
The structure $A$ is minimal: the induced structure on $I$ is strongly minimal so given a definable set either the projection to $I$ is cofinite or its complement is. Since the fibers of $I$ are finite, it follows that every definable set is finite or cofinite.
But $A$ does not have the NIP: in a saturated model there is a copy of an infinite atomless boolean algebra, and these do not have the NIP
