An interesting question. Terrible is not describing the physical look of Melko, but rather referees to the feeling one would get to come into the presence of the most feared being in all of Middle Earth.
Firstly, Meko wanted to look threatening, not ugly, that would probably lose him his respect, fearful. If you have ever seen
Morgoth's Ring, or
The Lays of Beleriand, these are some of my favourite illustrations of Melko. A Dark Lord, not necessarily ugly, but someone you wouldn't like to meet all the same.
It is not unlikely that Melko (in his early days) would have appeared as a fair creature, as Sauron did in later days. But I think it says somewhere that he keeps his form of a Dark Lord. Because Tolkien gives no in-depth description of Melkor at any point I am aware of, we cannot really say what Tolkien intended him to look like. I suppose its all up to our own imaginations.