Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?
Should I include this algorithm in $\mathbb{P}$?


Yes. Since the algorithm is asymptotically bounded above by $O(n)$ the algorithm is in $\mathbb{P}$.


  If zero $\in O(1)$, . . .


Zero is in $O(1)$. 


  . . . so often material I study from doesn't distinguish between Big-O and Big-Theta


big-O pertains to an asymptotic upper bound, where big-Theta pertains to an asymptotic tight bound.

The formal definition: $$f(n) \in O(g(n)) \iff \exists N_0,c\in\mathbb{R}^+ \text{ such that } n&gt;N_0 \implies 0 \leq f(n) \leq cg(n)$$ Also, $$f(n) \in \Theta(g(n)) \iff \exists N_0, c_1, c_2 \in \mathbb{R}^+ \text{ such that } n&gt;N_0 \implies c_1g(n)\leq f(n)\leq c_2g(n)$$

For example, $f(n) = n^2 + 3n \in O(n^3)$ and $f(n) \in O(n^2)$. But, $f(n) \not\in \Theta(n^3)$, yet $f(n) \in \Theta(n^2)$. 

We can't use $\Theta(n^{O(1)})$ to describe $\mathbb{P}$, as $O(lg(n))$ isn't in $\Theta(n^{O(1)})$, but is in $O(n^{O(1)})$ (and is in $\mathbb{P}$).