In addition to the ones already said:
Joel Grey- "Comedy Tonight"
Rita Moreno- "Apache Dance"
Paul Williams- "All of Me"
Lena Horne- "Ragg Mopp"
Bruce Forsyth- "In a Little Spanish Town" (a personal favorite)
Sandy Duncan- "A Nice Girl Like Me" (what an opening!)
Ethel Merman- "Java" (this one's just fun)
Don Knotts- "Sweet Gingerbread Man" (perhaps my earliest memory of TMS)
Rich Little- "Chanson D'Amour" (great way to begin)
Lou Rawls- "Groovy People" (nice energetic opening)
Jaye P. Morgan- "Tweedily Dee" (I don't know why, this opening is just nifty)
Roy Clark- "Rocky Top" (sets the mood well)
Jean Stapleton- "Tico Tico" (sets the mood even better)
Helen Reddy- "Stayin' Alive" (again, mood)
Spike Milligan- "Oklahoma" (colorful, energetic, fun, and just plain amusing)
John Denver- "Why Can't We Be Friends?" (good large-scale number with a look and feel that ushers in the new season quite nicely)
Shields & Yarnell- "Take a Chance on Me" (just a good #)
Phyllis George- "Yes, We Have No Bananas (Swedish version)" (different, but in a good way)
Christopher Reeve- "Disco Frog" (classic)
Alan Arkin- "Devil Went Down to Georgia" (cool)
Diana Ross- "I Go To Rio" (another personal favorite)
Loretta Swit- "There Ain't Nobody Here But Us Chickens" (mood, ushers in the new season)
Tony Randall- "Yakety Yak" (a lot of fun)
Melissa Manchester- "Tumbling Tumbleweeds" (freakin' awesome how they did that)
Gladys Knight- "Night and Day" (very good, adds spice of variety to the episode)
David "Gorgon Heap" Ebersole