Sorry to hear about the hassles you went through to get NodeXL installed. As you've seen, it requires a few other pieces of software to run, and getting them all working in a "locked down" environment like yours can be a challenge.
NodeXL has two types of vertex labels, and I assume that you are referring to the type that appears as an "annotation" next to the vertices themselves. To change the font size for those (and I'm talking about version 184.108.40.206 here; the steps are slightly
different in earlier versions), do this:
1. Click Graph Options at the top of the graph pane. If the graph pane is narrow, the Graph Options button will be hidden under a "down arrow" icon.
2. In the Graph Options dialog box, click the Other tab.
3. On the Other tab, click Labels.
4. In the Label Options dialog box, click Font.
The font you select applies to all vertex labels and cannot be changed for individual vertices.