The comment of Robert brought me onto the right track. Say $I=\{1,...,m\}$, then
\begin{align} \Bbb R^n\setminus C^\circ &= \{\,y\in\Bbb R^n\mid \exists x\in C\colon\langle x,y\rangle >1\,\} \\&= \{\,y\in\Bbb R^n\mid \exists x\in\Bbb R^n\colon p_1(x)\le 1 \land\cdots\land p_m(x)\le1 \land \langle x,y\rangle>1\,\} \\&=\pi\, \{(x,y)\in\Bbb R^n\times\Bbb R^n\mid p_1(x)\le 1 \land\cdots\land p_m(x)\le1 \land \langle x,y\rangle>1\,\}, \end{align}
where $\pi$ is the projection $(x,y)\mapsto y$.
So $\Bbb R^n\setminus C^\circ$ is the projection of a semi-algebraic set. By Tarski-Seidenberg $\Bbb R^n\setminus C^\circ$ is a semi-algebraic set, and so is its complement $C^\circ$.
What I don't yet see is why it is necessarily of the form $(*)$, i.e. using only intersections.