When my little girl was around 3.5 she was captivated by Howl’s Moving Castle.
I have Porco Rosso on for my 1 year old right now.
She is mildly entertained, but it isn’t exactly engaging for her.
Just FYI.
I’d say if you want to watch them with your son, your are best off waiting for Ponyo.
He might enjoy Kiki, but as other’s have noted, thematically it is far more likely to resonate with an older child. The others are similarly, if not more, “adult”.
Naussica is an excellent film, but frankly, I’d consider it PG-13 from a rating standpoint, and would not recommend it for a pre-teen. The story line is, as you thought, complex; and there is enough violence that I’d recommend watching it first alone before deciding if it were suitable.
Grave of the Fireflies if you want her to turn into an emo or something. :smack:
I was well into my 20’s the first, (and only), time I’ve ever watched Grave of the Fireflies. One of the best movies I’ve ever seen and one of only two movies that have ever made me cry in front of other people. The DVD case has sat on my shelf undisturbed for over four years now, and there it shall remain.
Not recommended for young children. Especially not ones who can grasp the concepts of death and mortality.
I watched it about two years ago. I was working my way down a list of animes I should watch and that came up. I asked people in the MTGO clan I was part of during that time if they liked it and everybody said it made them cry. So I watched the movie as a challenge but it beat me, even though I was expecting it. 
In case it isn’t very, very obvious at this point I’ll make it obvious:
DO NOT SHOW GRAVE OF FIREFLIES TO A 3 1/2 YEAR OLD. IT IS FOR ADULTS AND IS EXTREMELY TRAUMATIC!!!
Great movie, though, but clearly for adults.
OK, all jokes aside, I see nothing wrong with showing GotF to a child. Not a 3.5 y.o, I’m with you there, but a 10 y.o. or so, sure. I don’t know why everyone thinks it’s soooo traumatic that they can’t watch it again. I really don’t. Yes, it’s sad. IMO, sad is to be valued, not avoided. Plus it’s beautiful - beautifully drawn, beautifully written. I don’t avoid looking at Guernica despite it being the 2D embodiment of human misery, I don’t avoid reading Flowers for Algernon because of the ending. Same-same for GotF.