[Elladan and Elrohir]

I have always viewed Gothmog as an orc. Maybe this is incorrect, but it seems more likely to me than him being a Nazgul.

Throughout LOTR, we are never once given the name of a Ringwraith. In fact, only one is given a title - the Witch-king. The only named Nazgul is Khamul the Easterling, and that only in "The Hunt for the Ring" in Unfinished Tales. So it seems quite remarkable to me that we would see a Nazgul mentioned by name and yet not identified as a Nazgul, within the text of LOTR.

Meanwhile, Orcs are named several times - Ugluk, Grishnakh, Shagrat, Gorbag are the most famous; though you also have, among others, Lagduf, Muzgash, Lugdush (which actually seems to be a combo of the two, now that I think about it), Mauhur, and Snaga; the latter being a commonly used title for lesser Orcs by the Uruks. In The Hobbit, we have Azog and Bolg. There may be named Orcs in The Silmarillion, but if so, I do not recall any.

On the other hand, all these Orc-names are apparently in Black Speech, while Gothmog is an Elvish name. Which could point to him being a Man - or of course a Ringwraith.

Gothmog is described as the "lieutenant of Morgul" - as already pointed out, the Witch-king is called the "Morgul-lord", so it does make sense that Gothmog was his second-in-command.

There are only three comparable positions among Sauron's forces. First, the Mouth of Sauron, who was Lieutenant of Barad-dur. Second, Shagrat, who is I believe described as "Captain of the Tower" of Cirith Ungol. And finally, Khamul, who was the captain or lieutenant (I cannot remember which) of Dol Guldur.

A Man, an Orc, and a Ringwraith, respectively, as you will notice. So apparently there would be precedent for Gothmog to be any of these races.

The only two other possible factors I can think of that might have bearing on Gothmog's race are Grishnakh and Gorbag. Grishnakh had some position at Lugburz, I believe; and Gorbag was very likely some sort of lieutenant or sergeant for Minas Morgul. Not having the book to hand, I can't ascertain either one of those, but they sound right.

Regardless, there's not enough room to make a certain conclusion either way. So I guess I'll stick to his being an Orc.