Preferably free - kids shows / films from iTunes are an obvious one.
Bubbles. Works great on iPad also. It's important for toddler software to be ad free, since they will click on links.
There is a free limited version of Sound Touch but personally I think the full version is well worth the few bucks it costs.
My daughter went through an obsession with Monkey Preschool Lunchbox. I can vouch that it's highly educational, too. She became much better at counting (after about 2 weeks, she no longer needed to count out groups of 10, she could just look at a collection and say "there are 8 bananas.").
Not free, but the various Dr. Seuss apps are great, as they will read the book out loud at the child's pace. I also always have "Animal Sounds" at the ready.
For free, my daughter spends more time browsing photos of herself, family, and friends (in that order) than doing anything else. Go figure.
Oh, we get a lot of mileage out of (pirated) episodes of Dora the Explorer.
Monkey Kick Off keeps my daughter amused for hours on end - so much so that she gets cranky when the phone rings and I have to take it off her!
Not free, but check out mouthoff. Great for kids I'd imagine. http://iphone.ustwo.co.uk/iphone/apps/showusyourmouthoff/
You mentioned that videos/shows would be a priority. Take a look at the app called WEET WOO. It does something very simple: It presents an interface for you and your kid to choose from a big selection of kids' videos and shows that are actually stored on YouTube, including some fun educations series, etc. They are categorized (Animals, Humor, etc) so you can find what you want. But, naturally, the main deal is that you know that anything you stumble on is going to be fun and educational for the kid... not some lame music video or whatever.