My daughter is six and super-happy with the Nintendo DS. I have a 3DS that she also plays on sometimes. When she was 4, we bought one of those child-hardened Kindles and enrolled her in Amazon Freetime; she loved it.
Exactly the same progression with my five year-old. He still uses his hardened Kindle with Freetime, but for most gaming, really likes his DS I restored from a broken state on the cheap.
