Most of them need you to know the source material (Harry Potter, Star Wars, etc...) to really enjoy them, though.
But yeah, they're pretty fun in a "blow up everything in the scenery" sort of way ^^

Deathtrap Dungeons teaches children that life is unfair...

Being incredibly unbiased I must suggest a racing game, perhaps Race The Sun ?
That game has simple mechanics and the screen is not cluttered with things so its easy to see.

Otherwise I think platformers are an ideal option, like Rogue Legacy and similar.

There's always minecraft. Then there's also the Lego Games.
Another good idea would be to grab a adventure game like The Secret of Monkey Island and playing through it together with your kids and solve all of the puzzles as a team. Kind of a sweet bonding experience I think.

Now THAT'S a list! I'll definitely reference this as I go. The oldest is 4 so many of these are still too "scary" or violent for them, but I have always love the idea of introducing them to old-school games first.

Thanks, phalanges!

I used to play Super Solvers: Outnumbered. Decent math game, if I remember correctly.

I'd also throw in Cosmo's Cosmic Adventure, which I think is part of the 3D Realms Anthology!
Oh, and Commander Keen: Keen Dreams. It's a way less violent version of the game, which has you throwing flowers at living vegetables, so it may be right up their alley! (Or not, if you're trying to teach them veggies are good for you.) :D

Did anyone already suggest the Giana Sisters reboot? Seems quite child-friendly to me, and while the gameplay can be challenging it isn't really complex.

Costume Quest perhaps? Chronology? Oh, Mousecraft would be great too!

That new-ish release, Never Alone? Octodad?

That's about all I got. Most other games include combat/violence or would be too complex for small children.

The Crazy Machines bundle from the Bundle Stars (if you want to get the series cheap). A bit of brain teasing and fun to play.

https://www.bundlestars.com/en/bundle/crazy-machines-bundle-reloaded

And maybe some Sonic games:

http://store.steampowered.com/sub/26498/

The All Stars Racing games are fun, so if you can grab them in a sale or a bundle, the kid will have a blast.

Journey of a Roach might be worth checking out. It's a simple, wordless adventure game with a walking-on-walls gimmick.

Your roach seem to be able to die, but at least this look a lot more child-friendly than that other roach-sim, Bad Mojo.

4 might be a bit too young to follow it, but from my own experience with a niece of 7 at the time, I'd second "Night of the Rabbit" as a good choice for when they're a bit older.

Minecraft in creative/peaceful mode is also perfectly doable though - says the 4 year old nephew who hasn't wanted to do anything else since he was introduced to it. It's purely a builder game when set to play that way.

+1 to the LEGO games.
The LEGO Movie game is great (as is the movie itself) and very much suitable for a kid. And you dont really need to understand the movie and its source material to understand the game (in the way that you might need to with e.g. Star Wars or the like)

It seems to be a rather difficult adventure game though, judging from my own experience and what others write about it? I got stuck very early in the beginning and I've been playing point and click adventures for over 20 years ... (Not that this necessarily means anything, but the puzzles seem a bit obtuse at times and hints sparse.)

Thanks LiquidOxygen! Commander Keen looks like an awesome intro to old-school graphics. Cosmo's Cosmic Adventure has been Wishlisted.

I couldn't find Super Solvers - any idea where to look?

Thanks again!
J
This is great - thanks! I had a few of these on my list already but added Costume Quest, Mousecraft ,and Octodad.

I know this thread is kind of old, but the games of my childhood that hold a fond spot in my heart are (basically all) the Humongous Entertainment games, the entire collection of which you can find here:
http://store.steampowered.com/sub/42723/
I also remember the games from The Learning Company such as the Super Solvers series, but the company pretty mush crashed in the early 2000s and I'm not sure if it's possible to find/play any of them anymore unless you have an old computer or use an emulator.
Edit: Oh, hello, seems like a good deal of TLC games are considered abandonware now and can be not only downloaded, but emulated online for free. These are some which I played as a kid:
http://www.myabandonware.com/game/super-solvers-treasure-mountain-s4/play-s4
http://www.myabandonware.com/game/super-solvers-outnumbered-115
http://www.myabandonware.com/game/super-solvers-challenge-of-the-ancient-empires-113
Might want to wait until they're a little older for these ones, though, as they were intended for ages 7 or so and up, and the last two could be a little scary for them.
Edit #2:
I found a list of TLC games on the site, although these aren't all of them that they offer. The Cluefinders and Reader Rabbit were pretty good educational series.
http://www.myabandonware.com/browse/developer/the-learning-company-inc-bv/

This might qualify, too: Metamorphabet.