Integer solution

I doubt that the lower bound $\frac{p-1}{2} - 2cp^{1/3}$ holds for all $p$. Here is a proof for the weaker bound $\frac{p-1}{2} - cp^{1/2}$.

First of all, the inequality $\frac{p-1}{2}-cp^{1/2} \leq f(x_1,x_2,x_3) \leq \frac{p-1}{2}$ is essentially equivalent to
$$p- O(p^{1/2}) \leq (2x_1+1)(2x_2+1)(2x_3+1) \leq p.$$

Let us take $y=\left\lceil\frac{p^{1/3}-1}{2}\right\rceil$. Then
$$p \leq (2y+1)^3 < (p^{1/3}+2)^3 < p + O(p^{2/3}).$$

Define
$$z = \left( \frac{(2y+1)^3 - p}{4(2y+1)} \right)^{1/2} .$$
Clearly, we have $z=O(p^{1/6})$.

Now, let us take $x_1 = y$, $x_2 = y - \lceil z\rceil$, $x_3 = y + \lceil z\rceil$ so that
$$(2x_1+1)(2x_2+1)(2x_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1)$$
$$< (2y+1)^3 - 4z^2(2y+1) = p.$$
On the other hand, we have
$$(2x_1+1)(2x_2+1)(2x_3+1) = (2y+1)^3 - 4\lceil z\rceil^2(2y+1)$$
$$> (2y+1)^3 - 4(z+1)^2(2y+1) = p - O(p^{1/2}).$$