Hi,
I third the recommendation for starfall. Free and lots of levels from learning abcs through to reading stories.
I ran across a used copy of Reader Rabbit software/books which I'd heard good things about, but the books were dull and the computer part too slow to load (maybe just my slow computer) for my DSs interest.
If you are looking for books, a little book my son (now 2 and 3 months) loved was Mouse Makes Words. By Kathryn Heling. A cute mouse lugs around letters and takes away one letter, puts another in its place and makes various 3 letter words. They have a couple copies at my library so maybe also at yours.
We enjoy the game "I see something that starts with". At first we played it, "I see something that starts with the sound", and I would pick very easy words such as I see something that starts with mmmm, and point to myself. Great car game and its phonics. My son still often picks things that he sees in his mind rather than in reality, but its reliably some species of dinosaur so I can still guess, LOL.
As far as wondering whether its even okay to do any instruction at all, there's no particular reason to wait to introduce information related to reading. Its a set of symbols and rules, sort of like cooking, which we let them help with at a young age -- finding the word eggs in a book isn't that different from finding the real eggs in the fridge.
Polly
