My DS (who is now 6) went from Sesame Street and clips of the Muppet Show to Word World, Super Why, Between the Lions, and Dinosaur Train before venturing to Cyberchase and Magic School Bus. He has watched some Sid the Science Kid, Arthur, Clifford the Red Dog, and Curious George though, but I'm not crazy about these shows. He occasionally watches clips of Word Girl too, which is good for vocabulary words.
There's a ton of older (original) Sesame Street clips on YouTube if you haven't seen them as well as the other shows mentioned. There's a also a ton of stuff on the PBS website (
http://pbskids.org/).
Of course, you could pick up some DVDs at the library of some of these shows too, though not so much of the original Sesame Street unfortunately

.
Geez, I really love Jim Henson and miss those old Muppet Show and Sesame Street shows but I do like Super Why, which is charming and educational, and the Magic School Bus and Cyberchase (Christopher Lloyd aka Jim on the old TV show Taxi is excellent as Hacker).
I actually had an epiphany one day last Feb after my DS watched a clip of Cyberchase. He (aged 5 then) said the word tessellate, defined it, and then showed us what it meant with his Melissa & Doug blocks. I nearly hit the floor and thought then that my son was possibly eg/pg. So you never know what your child/ren may pick up from these shows.