I think that in terms of early diplomacy ( i say early, since it doesn't matter by later into the game anyway) is to ally with EVERYONE, and don't push for Tunis. if you let the Scilian take Tunis they usually won't bother with going all the way to Algier... having a real garrison helps too of coruse.

in the early moves, just head for Timbuktu and Arguin + Valencia and if your fast enough, Zaragosa . if you ally with both the Spainards and Portogusis I find that they usually start fighting themself and/or they'll stick with you with the other (usually Spain) attacks. this seems to still work fine in H/H . by allying with everyone anywhere near you (the Iberians / French / English / Italians / Dens etc..) you usually buy some time.

I tend to wait till the first Crusade is called to turn aggressive.