There is thought to be a "critical period" for language learning that ends at about 12 years old, which coincidentally is just about when most American schools begin teaching languages.
: After that period, it is much harder to learn a language and much harder to speak it without an accent. So early language learning is a great idea! There's also some evidence that kids who study foreign languages at an early age have an easier time learning yet more languages later in life.
When I was 4, I took a summer French class taught by a Quebec native who had moved to our town; she held it at her house for only 4 or 5 kids about 4-8 years old. She had some pictures for us to color and label, pointed to things and told us their names in French, taught us some songs, etc. It was great! 25 years later I remember about 75% of what I learned, and I also remember a lot of the Spanish words from "Sesame Street", whereas I took 3 years of high school German much more recently but remember only about 10%.
If you can find a native speaker of some language who is willing to spend an hour a week just hanging out talking with your child, that seems to me like the best approach--even better if the person also has a young child who is fluent in the language!
Another approach is to have your whole family try to learn a language together. Spanish might be a good choice because you already know some of it. Get a dictionary and put little signs on everything around the house. Get a tape with some songs and learn the sounds without worrying about what they mean; then later look at the lyrics and translate them and find out what you've been singing! If your daughter can read, rent Spanish movies with English subtitles so she can practice two things at once! Look for a first-year Spanish textbook in used bookstores, and even if she can't read, you can use it to learn dialogue and teach it to her so you can talk with each other about weather, food, and other everyday topics.
As for videos, some kids at church are really pleased with their Spanish video featuring someone called Muzzy....