In my experience (mostly emperor and immortal) the first bribe is always the most expensive one. If two civs have fought relatively recently it's usually possible to bribe one of them (or even one of their friends) into declaring war for relatively cheap. To get the first one going, remember that if Shaka is bearing down on you with a massive army of doom you don't necessarily need to get him to declare war on someone else - it's enough to get someone else to declare war on him. It's usually possible to find someone to do it, though it may cost you some luxes and a significant portion of your income.