I'm leaning towards Kuche now. Map making was the right choice, since we've made it clear to both teams we have contact with that it'd be our next tech. I have no problem making a lopsided deal to get them CoL since they can then start on the Republic.
I really don't want to enter any sort of gpt deal with anybody as that stalls our own research capabilities. Kuche has been offering frankly better and more even (over time) tech for tech deals, and, as Cyc pointed out, they are in a much worse position diplomatically than the Brotherhood (so we should be able to secure that deal). The only thing I see the Brotherhood offering at this point is the Republic faster. I can live with putting off our revolution for about 12 turns, besides we'll be able to crank out some dromons (and do some more expansion) during that time.
The other advantage with dealing with Kuche is that we don't have to fight them right away. We can use our dromons to their full potential by pillaging the coasts of the other continent. Since the Brotherhood is seafaring, we might be able to put ourselves in 1st for GNP if we destroy enough improvements. At any rate I don't think invading Kuche will be easy at all (especially if we're up against Samurai), but we're in a great position for coastal plundering.
I think we should apologize for the delay to Kuche, tell them we're Byzantium (that's why we went for MM), accept their deal and get them CoL ASAP. And tell the Brotherhood to guard their coasts.
EDIT: I don't think we can really wait for too long, as either team will assume we're dealing with the other team if we wait for that long (especially Kuche, we've been stalling for too long). I really don't expect Anarchie to show up soon, the Brotherhood wouldn't have asked us not to meet them if they knew they were on the way.