In this work we present a comparative investigation of the electronic structures of NbO$_2$ and VO$_2$ obtained within the combination of density functional theory and cluster-dynamical mean field theory calculations. We investigate the role of dynamic electronic correlations on the electronic structure of the metallic and insulating phases of NbO$_2$ and VO$_2$, with focus on the mechanism responsible for the gap opening in the insulating phases. For the rutile metallic phases of both oxides, we obtain that electronic correlations lead to strong renormalization of the $t_{2g}$ subbands, as well as the emergence of incoherent Hubbard subbands, signaling that electronic correlations are also important in the metallic phase of NbO$_2$. Interestingly, we find that nonlocal dynamic correlations do play a role in the gap formation of the (bct) insulating phase of NbO$_2$, by a similar physical mechanism as that recently proposed by us in the case of the (M$_1$) dimerized phase of VO$_2$ (textit{Phys. Rev. Lett. 117, 056402 (2016)}). Although the effect of nonlocal dynamic correlations in the gap opening of bct phase is less important than in the (M$_1$ and M$_2$) monoclinic phases of VO$_2$, their presence indicates that the former is not a purely Peierls-type insulator, as it was recently proposed.