Here is a bound in the case $n=2$.

Suppose $\phi$ is a cocycle with nontrivial cohomology class and $\phi(x,y)=0$ for at least $(1-\epsilon) p^2$ pairs $x,y$. Then $\epsilon \geq 1/8$.

Proof: Without loss of generality, the class of $\phi$ is the standard generator of $H^2(\mathbb Z/p, \mathbb Z/p)$. It follows that $\phi$ arises from a lift $l \colon \mathbb Z/p \to \mathbb Z/p^2$ where $l(x) \equiv x \mod p$, taking $\phi(x,y) = (l(x+y)-l(x) - l(y))/p$.

So we have $l(x+y) = l(x)+l(y)$ for all but $\epsilon p^2$ pairs $x,y$.

Now fix $a \in \mathbb Z/p$. What is the probability that $$ l(b) + l(a-b) = l(c) + l(a-c)$$ for $b,c$ random?

Well, it is the probability that

$$ l(b) - l(c) - l(b-c) = l (a-c) - l(a-b) - l(b-c)$$

and both pairs $(c,b-c)$ and $(a-b,b-c)$ are uniformly distributed, so both sides vanish with probability $1-\epsilon$ by assumption, so both sides are equal with probability $1 - 2 \epsilon$.

By linearity, it follows that there exists a single $c$ such that $$ l(b) + l(a-b) = l(c) + l(a-c)$$ with probability at least $1-2 \epsilon$. So there exists $f(a)$ such that $$l(b) + l(a-b)=f(a)$$ with probability at least $1-2\epsilon$.

Next let's check that $$f(a) + f(b) = f(a+b).$$

Well, we know for $c,d$ random that we have both $f(a) = l(c) + l(a-c)$ and $f(b) = l(d) + l(b-d)$ with probability at least $1-2 \epsilon$ each, so at least $1-4\epsilon$ together.

We have $l(c) + l(d) = l(c+d)$ and $l(a-c) + l(b-d) = l(a+b-c-d)$ with probability $1-\epsilon$ each, so all four events have probability at least $1-6  \epsilon$ together. In this case, we have

$$ f(a) + f(b) =  l(c) + l(a-c) + l(d) + l(b-d) =l (c+d) + l(a+b-c-d) $$ which equals $f(a+b)$ with probability at least $1-2\epsilon$.

So $$f(a) + f(b)= f(a+b)$$ with probability at least $1-8 \epsilon$. If $\epsilon< 1/8$, then both sides are equal with positive probability. But both sides are deterministic, so both sides are equal. Hence $f: \mathbb Z/p \to \mathbb Z/p^2$ is a group homomorphism with $f(x) \equiv x \mod p$. But this is impossible, so $\epsilon \geq 1/8$.

----

Let me explain the connection to computer science. This proof relies on an algorithm which, given a black box that computes the function $l \colon \mathbb Z/p \to \mathbb Z/p^2$, computes the homomorphism $f \colon \mathbb Z/p \to \mathbb Z/p^2$ (i.e. sample $l (b) + l(a-b)$ a large but bounded number of times and take the plurality vote). 

The algorithm as stated is not very useful, because its output cannot exist and thus its input does not exist, but a similar algorithm works for general groups (constructed by Blum, Luby, and Rubinfield in their paper [Self-testing/correcting with applications to numerical problems][1]).

The advantage of this algorithm is that the input needs only be approximately linear (which means it could fail to be linear on exactly the inputs you care about) whereas the output is exactly linear (and can be calculated, with high probability, on the inputs you care about). Because approximate linearity can be tested by checking enough examples, this allows an untrustworthy source to prove to you the existence of a linear function with certain properties in a short amount of time.


  [1]: https://www.sciencedirect.com/science/article/pii/002200009390044W