I love origami and doing it with young kids can be quite a test of patience for everyone. I found this lovely simple butterfly a few years ago. I've used with kids as young as three and they have been quite successful at it.
Rather than recreate a wonderful tutorial, I am going to point you to it here.
This butterfly is symmetrical and could be colored like a real butterfly.