There is absolutely no reason that aliens must be humanoid. Star Control made that clear.
You can imagine the first contact between the Earthlings and the Chenjesu:
Marines enter the alien shop that has just landed on earth:
Inside, a bunch of crystals are embedded in a table.
Soldier 1: "There appears to be no life on board."
(voice) We live!
Soldier 2: "Who said that?"
(voice) We said that.
Soldier 1: It's coming from near the table.
Soldier 2: Check under it!
(voice) We are the Chenjesu.
Soldier 1: I think the crystals are talking.
Soldier 2: Perhaps it's a communication device.
(voice) No, we ARE the Chenjesu. And your world, and all you know, are in danger!