Walter Koenig as Bester in Babylon 5. I know, he becomes major later on, but he starts minor and is wonderfully evil and memorable.
Clem from Buffy. 
Lwaxana Troi.
Lady Heather from CSI. I always thought her relationship with Grissom was deeper and more meaningful than his with Sara.
How about a couple of oldies:
Lance White (Tom Selleck) from The Rockford Files - “Clues just turn up Jim.”
Gandolph Fitch (Issac Hayes) from Rockford - “Hey Rockfish”
Elliot Carlin (Jack Riley) from *The Bob Newhart Show *- “You know its a bad party when Elliot Carlin is the happiest guy in the room.”
Edith Keeler
She’s a good one, but I think Emil Skoda, played by the incomparable J.K. Simmons, blew her away in the memorableness department.
Ainsley Hayes from The West Wing just stole every episode she was in.
Donnie DiMauro from Just Shoot Me
“Chicken pot, chicken pot, chicken pot pie!”
Bebe, Frasier’s agent, on Frasier
Soup Nazi, anyone?
Marcy Rhoades D’Arcy, Married with Children. So much fun to see Al and Peg’s constant bad influence sand off the sweet yuppie facade to reveal the hard-hearted, anger-filled flaming bitch underneath. Fine actress too and I think the prettiest female cast member (yes, counting Christina).
Q from ST:TNG
Kosh from B5
That wasn’t Flagg, it was a South Korean officer.
Yeah, there were a ton of great minor characters on Seinfeld. Many of them (like the Soup Nazi) were one-off characters, but some of the great recurring ones were:
Newman
Uncle Leo
Tim Whatley
George Steinbrenner
Mr. Pitt
J. Peterman
Puddy
Kenny Bania
Jackie Chiles
Crazy Joe Davola
Poppy
The Maestro
One/three of my favorites: Larry, Darryl, and Darryl from Newhart.
Vito Giotto, in the Dick Van Dyke Show episode, “Give Me Your Walls!” A great performance by Vito Scotti.
Reading the thread title, I immediately thought of Lenny and Squiggy.
That reminded me of Leather Tuscadero from Happy Days.
Since we were both beaten to Sally Sparrow, I’ll add Jenny, a real Doctor’s daughter as The Doctor’s Daughter.
Gary Jones, as CMSargeant Walter Harriman on “Stargate SG-1” who did a great job as “The Chevron Guy” and went with Hammond of Texas when he assumed command of the “Promethesus” to do battle with the false god Anubis in “Lost City”
Jenny Tomasin as scullery Ruby Finch (Lord Bellamy had to ask Mrs Bridges what her last name was after some 20 years of service) on “Upstairs, Downstairs”
If a main actor in a recurring role is needed. Hans Conried as Uncle Tonoose in “Make Room for Daddy”.