A mix of tall shrubs and small trees would be nice if you can plant in staggered clumps -- not a straight "one-dimensional" row. A layered effect with taller plants in back next to the fence, stepping down to mid-height and low shrubs and then maybe grasses/perennials would provide dense privacy screens and look beautiful.

Clumping bamboos (Bambusa spp.), banana plants and other tall, dense plants in back, then maybe fruit trees mided here and there, such as your cherimoya, and mid/lower growing lush foliage around them.

I'd like to suggest palms because their clean trunks will not crowd out your your backyard and yet their fronds at a higher level might effectively screen your space. I would be tempted to try a line of sight sketch. Imagine a line from their balcony down to ground level at the edge of your house. Place your back fence in the profile (use a manageable scale) and you will get an idea of how high the canopy of the tree line has to be. I recently saw a good example of this kind of screening achieved by planting a mixture of Chinese Fan and Queen palms.