We started Mandarin when each dc was 3. We've used a "play tutor," who pretty much plays games, colors pictures, sings songs and tells stories in Chinese. Its a very gentle, fun introduction to the language. We live in China, so we also hear it spoken around us everyday. I personally would not attempt such a difficult language in a place where it isn't spoken regularly. It is just so different from English, and you really need a native speaker to practice it with.
This year we began Prima Latina, and dd LOVES it! She wants to pray in Latin before our meals and inserts random Latin words into her sentences. I'm enjoying it, too, and find it much easier than learning Thai and Mandarin has been.