I also played two games with my niece Amber, who is three and a half. Hey, That's My Fish is a fun penguin-themed game. You move penguins across a hex board, picking up the penguins' starting tile (gaining the fish that were on it), thus blocking other players and eventually trapping all the penguins. Amber was able to play but not really engage in strategic decision-making. Marissa won handily.
The second game was Hisss which is much more of a children's game based on matching colors to grow a snake, then claiming it by finishing its head or tail. It's not quite trivial, though--- you sometimes have a choice as to which snake (or which end of a snake) to extend, whether to combine two existing snakes, or how to use a rainbow-colored tile. Keeping track of which heads and tails have been seen, and adjusting your longer- vs. shorter- snake preference based on whether you are currently winning, could result in a small advantage over players acting randomly. (Somebody over at boardgamegeek made some initial forays into trying to quantify the benefit.) Marissa won this one too.