I didn't read all the postings, but my dd's got a good start using www.headsprout.com. DD9 was 18 mo and only did the first "free lessons". DD7 was closer to 3 and did the first series of lessons.

DD7 liked the silly stuff in between the lessons, always something entertaining and interactive. (helps with mouse skills as well)