Na, dann gratuliere ich zum OWD und versuche mich mal dran etwas Licht ins Dunkel zu bringen.
Es ist fast normal, dass man sich anfangs nach bestandenem Kurs, ohne Ahnung und Kontakten zur "Tauchscene", etwas verloren in der Tauchwelt vorkommt.
Ich kann mich da auch noch dran erinnern...
Kannte damals auch niemanden der dem Hobby nach ging und suchte auch entsprechenden Anschluss.
Gleich nach der OWD Ausbildung ist es meiner Meinung nach "Pflicht" sich an eine Basis bzw. Verein dran zu hängen, um dort bei Ausfahrten enstprechend Erfahrung zu sammeln.
Du lernst so die Tauchgewässer in der Gegend kennen, Dir werden die Einstiege gezeigt, kannst Kontakte zu andren Tauchern knüpfen etc..
Vielerorts gibt es auch Tauchertreffs oder organisiertes After Work Tauchen, auch das ist für Anfänger bestens geeignet da diese Tauchgänge meist geführt werden.
Ihr habt also keinen Stress und könnt euch aufs wesentliche konzentrieren, also aufs Tauchen, das reicht den meisten OWDlern am Anfang auch.

Daher würde ich euch Raten die ersten Tauchgänge genau nach diesem Motto zu machen und damit am besten schon in Deutschland anzufangen, also jetzt keine Pause machen und dran bleiben!
Je mehr Erfahrung Ihr auf eueren Trip mitnehmen könnt um so besser.
Ihr werdet bei diesen Veranstaltungen entsprechend Leute kennen lernen mit denen es sich dann auch ergeben wird Autark tauchen zu gehen.
Außerdem baut Ihr auch entsprechend Selbstsicherheit auf und irgendwann ist dann auch der Punkt erreicht an dem Ihr mal alleine zum Tauchplatz fahrt.
Ihr wisst dann worauf Ihr euch einlasst, kennt die Örtlichkeiten unter und auch über Wasser, findet den Weg zurück etc. und Ihr kommt mit dem Taskload zurecht.
Aber lasst es ruhig angehen, macht nichts wobei Ihr euch nicht wohl fühlt!
Beherzigt den Slogen: "Tauche innerhalb DEINER Limits und deines Ausbildungsgrades."
Ihr werdet mit 25 TG dann glauben Ihr wärt die "Supertaucher" um dann mit 100 TG festzustellen, das Ihr eigentlich doch "nix könnt" und Anfänger seid.

Um nun den Bogen auf deine Auslandsfrage zu spannen, ja auch dort ist es in genau eurer Situation absolut ratsam mit einer Basis tauchen zu gehen!
Ihr seid zwei blutige Anfänger und trefft dort unter Umständen auf euch völlig unbekannte Situationen...
Die Selbstsicherheit um dann mal alleine loszuziehen kommt von selbst, das merkt Ihr dann schon und wenn Ihr die Plätze mal kennt und auch wisst, dass Ihr euch dort nicht total vertauchen könnt etc. dann ist das auch OK. Dabei denke ich an sowas wie Hausriff Tauchen...
Leute mit gengu Erfahrung tauchen auch im Ausland teilweise autark, aber vieles läuft über Basen, da viele interessante Tauchplätze eben auch garnicht von Land aus erreichbar sind und man auf ein Boot der Basis angewiesen ist.
Das die Basis wissen will wie viele Tauchgänge Ihr habt ist auch normal, Ihr Checkt in einer Tauchbasis in der Regel zu Beginn ein.
Dort wird euer Brevet kontrolliert und eure Erfahrung abgeklappert.
Das dient zu allen deinen genannten Möglichkeiten, es kann sein, dass man auf gewisse Touren nicht mit kann, oder dann evtl. nur mit Guide.
Dein letztgenannter Vorschlag, dass man einen erfahrenen Taucher zu Seite bekommt, ist manchmal der Fall...
Aber oft ist das von dem erfahrenen Taucher garnicht gewünscht, der hat nämlich nicht zwangsweise Bock in seinem Urlaub das "Kindermädchen" zu spielen und in seinen Augen Flossenwäscher Tauchgänge zu machen. Das hast Du eher zuhause bei Vereins oder Basenausfahrten, das sind Tauchgänge die haben die alten Hasen schon duzende male gemacht, da nehmen die in der Regel gerne Anfänger mit.
Das kannst Du hier auch oft nachlesen, dass gerade Tauchlehrer oder hoch Brevetierte Taucher im Ausland oft nur mit der gerade für die gepanten Aktivitäten ausreichenden Brevetierung einchecken, um genau sowas aus dem Weg zu gehen.

Das ist meistens nicht mal böse gemeint, aber da haben wohl viele schon schlechte Erfahrungen gemacht und einen Urlaub lang "bezahlenden Guide" auf diversen Basen gespielt.
Ablauf wie von Dir geschrieben, "normalerweise" schreibst Du eine Basis in der Nähe deines Aufenthaltsortes an und machst Dich schlau was dort so angeboten wird, gerade auch für euch als OWD.
Die erzählen Dir dann schon was die so treiben und wo du mit kannst und wo noch nicht.
Auch eine Tauchversicherung kann nicht schaden und ja es gibt Tauchdestinationen dort wird diese gefordert.
Die bekanntesten sind DAN oder Aquamed, diese Versicherungen enthalten auch immer eine Auslandskrankenversicherung, somit relativieren sich die Kosten etwas.
Ach ja, solltest Du dich für einen Verein entscheiden, dort ist im Beitrag meist auch die Versicherung mit drin.
Ich hoffe etwas zur Erleuchtung beigetragen zu haben.
Edit: Da überscheidet sich jetzt manches, da "zeitgleich" geantwortet.
