Well i'm doing several new countries every year on my own, now up to 40 with a few more to be visited this year, one of which should be Russia with its underground metro stations....
But i took my 6 year old up to Bali (yes you know, bogan central and all that) last year and he got to swim with some dolphins, stroke them and interact.. Just got back from another week up there and this time took him to Bali Zoo, bird park, butterfly park, reptile park, monkey forest, rice terraces and took him to show him a vlocano but by then rain clouds had come in and couldn't see much... So he got to hold lots of animals and insects that he might not have seen here, or certainly got to hold... So lots of nice memories being built up along with restaurants to eat at and flights and waterbom park and swims in pool without any 2nd mortgages needing to be taken out...
Next i might take him to Singapore or perhaps one of the pacific islands... After seeing so many animals he did say he wanted to be an animal trainer, so anything that helps concentrate his mind on becoming something sounds good to me.... As he gets older and can rough it a bit more and retain the memories i will probably take him to Africa to see some of the big 5 etc... I'm not personally one for art galleries all that much but i'm sure he would love some of the natural history and science museums in Wash DC, NYC, London and a few other places... But will probably save that for when he is in double figures...