However, I still don't understand why Andorians and Tellarites never appeared in the movies.
Ummmm, there were three Andorian Ambassadors (one male, two female) in ST:TMP, and two members of the Enterprise crew. Makeup by Fred Phillips.
Tom Burman put two Andorian admirals in ST IV, including one who was balding, in order to show off the latest advances in slip latex appliance work - no antennae joins needing to be hidden by a wig!
There was also the live-action Cadet Vanda M'Giia in the CD-ROM game, "Starfleet Academy".
http://andorfiles.blogspot.com/2009/10/mov-rogues-gallery.html
There were also two Tellarites in ST IV, both wearing Kazarite robes from TMP.
That they were all relegated to crowd scenes indicates that the directors were perhaps unsure about showing these makeups over longer periods, on actors with lines to deliver.