"Possibly" and "necessarily" seem very much like "exists" and "for-all", but does the following hold true: $\neg \square P \equiv \lozenge \neg P$ in the same way as $\neg\forall P \equiv \exists\neg P$ ?
From the definition of "necessarily" in my book, being that $P$ should be true in all possible worlds, it seems to be so.
A corner case will be if there are no possible worlds. In this case, the "necessarily" is vacuously true, so its negation is false; at the same time, there are no possible worlds whatsoever, so there's no world where $\lnot P$ is possible, so the right-hand statement is false as well.
Is this so, or is my reasoning flawed?
Yes. There's a strong convention that $\Box$ and $\Diamond$ are always each other's duals, even in special-purpose modal logics. When the propositional substratum is classical, this implies that $\neg\Box\equiv \Diamond\neg$ and $\Box\neg\equiv\neg\Diamond$.
For example, when $\Box P \leftrightarrow \neg\Diamond\neg P$ is an axiom (or the definition of $\Box$ as an abbreviation), you get these laws by either negating both sides or letting $P$ be $\neg Q$, and then applying double-negation elimination.
If one wants to define a system with two unary modal connectives that are not related in this way, one had better choose a different symbol for one of them.