Reader Rabbit was great. My daughter loved it. Very simple and engaging.
I’ll second Jumpstart Toddlers as a good start. Also Dr. Suess ABCs – lotsa places to just click and the animations do silly entertaining things.
The Putt-Putts are great as your kid gets more comfortable with the computer. Then move up to Pajama Sam as he gets older. Great stuff.
Two more threads on this topic:
http://boards.straightdope.com/sdmb/showthread.php?s=&threadid=112332
http://boards.straightdope.com/sdmb/showthread.php?s=&threadid=99687