I am trying to create a new feature class and when I right click on my project in Catalog, I do not have the option for NEW. See screenshot. Is this a permissions issue? Is the software not setup properly?
You need to right click a geodatabase rather than your mxd. Doing so should expose the "New" option you're looking for.
Right click on the folder where you want to save your data (H drive I'm assuming), select New > File Geodatbase. Then, right click your new geodatabase and select New > Feature class.