Fisher Price have a sizeable catalog of software, mostly on hybrid Mac / Windows CD. Even better, you don't have to buy it new, the 2nd user software stores always have a selection of titles available, all usually under £0.50 / $1.
So I've got through a number of titles with my (just turned) 4yo son, he's outgrown most of them already, but then he did start using my PMG4 when he was about 3 months old (before getting his own account on my Mac Pro at 15 months old - I can hardly ever get on it now). Some of the games for slightly older toddlers, ie. 3yo, 4yo, 5yo will go down a treat if you can spare the time to do all the stuf for them. Alas you need to play it their way, even if it's wrong.
There's also a lot of Flash content on the web for young ones, ie. the BBC CBeebies site, for up to 6yo.
Favourite game at the moment is an old copy of "The Incredible Machine" which I have to play under emulation, I solve the puzzle once, or start to solve it and my son takes over and re-solves it or completes it. I don't think it was meant for kids at all.
There was also a selection of keyboard bashing games with music called Giggles Baby Shapes and Giggles Baby My Animal Friends (and one more title I didn't get). I think they were for up to 36 months, but my son had outgrown the Animals title by 21 months and the Shapes title 3 months before that.
