I will warn you, though, that there are some people for whom this is an acquired taste. And there are many people who never manage to acquire this taste, the poor things. There are unfortunate souls who go to their graves claiming that cupuacu tastes like Vick’s Vapo-Rub. Sad, but true.
I very strongly second the recommendation that you head for northern Brazil, though. The variety and quality of the fruit is incredible. Mycroft Holmes hasn’t even begun to describe it. In addition to the fruits he’s already listed for you, there’s umbu, sapoti, camu camu…lots and lots more. Definitely check out the acai, though. If you’re in the US, in a place with a Whole Foods or a Wild Oats Market, you can get acai in frozen packets. I say, skip the already-sweetened stuff and go straight for the pure, deep purple stuff. You won’t be able to eat it straight from the packet, but you can whip it in your blender with a bit of juice (to start the blending action) and some honey. In Brazil, you’d use guarana syrup, but I haven’t found a source for that here. The stuff is pretty darn yummy when it’s made with honey, though, so the substitution is hardly a loss.
There are a bunch of Ecuadorian fruits that might be of interest to you. There’s a limoncillo, which looks on the outside like a tiny lime. You pop off the rind and suck on the pulp beneath. The stuff tastes kind of like an intense cross between a citrus fruit and a lychee.
There’s naranjilla, which, despite its name, is nothing like an orange, really–it’s got sour, sweet, and slightly bitter flavors all at the same time. It makes a truly wonderful juice.
You could check out the yummy little taxo, a close relation to the more common maracuja type of passion fruit. Maracuja is also delicious, btw, but it often needs a little bit of sugar to keep it from being too tart. Then again, so does graviola, which has a wonderful flavor.
Don’t forget guanabanas (I think they’re called “custard apples” in English, but I’m not sure), which can be truly creamy and luscious.
I’m not a fan of a fruit called a “babaco” (I think the stuff tastes like Lysol), but I met several people who were crazy for it.
The tamarind-like borojo is truly luscious when made into juices, though.