Möchte denn das eine Paar nach A, dass andere nach B?
Wenn dem so ist, würde ich gleich davon abraten. Das Ergebnis vor Ort kann schnell dergestalt aussehen, dass sich Paar X mit Paar Y verkracht, weil es einer Seite nicht so gefällt wie (vor allem vom anderen Paar) erhofft und sich Vorhaltungen gemacht werden.

Sucht euch lieber etwas, das alle anspricht, wo alle von vornherein sagen: "Ja, das ist toll, das machen wir!".

Im Zweifel würde ich Andalusien empfehlen, da dies von der Anreise deutlich kürzer und entspannter ist, und sich bei einem Streit (ja, das ist schnell möglich bei 4 Leuten aufgeteilt auf 2 Pärchen!) der finanzielle Verlust des dann vielleicht verhunzten Urlaubs im Rahmen hält.