Gotland rekommendera jag inte heller, visst naturen är helt underbart men det bli rätt sällan avslappnade kajakturer där. Alla stenar, raukar, öppet hav osv gör det rätt svårt att paddla tyvärr.
I Norge finns det såklart en hel del riktig häftig, och att börja lära sig där är inga problem OM man har ngn som lär ut. Är man uppvuxen där man ska paddla har man i alla fall lite koll hur tidvattnet och andra grejer funkar men resa man bara dit ta det en stund att förstår hur vädret och havet funkar just där man är. Ju längre upp man kommer ju plötsligare kan vädret ändra sig, dimman drar ihop sig riktig tätt och det blåser och har sig. Med ngn lärare som kan de trakterna bör det dock funkar fint - det finns ju de som bor i Norge och har lärt sig

Men jag vet inga kurser där på rakt arm.
I Sverige är vädret lite lättare samt att det även finns många riktig fina skärgårdar som både är vackert att titta på och dessutom kan man paddla i skyddade miljöer. Det finns ingen tidvatten heller.
Friluftsfrämjandet har ju redan nämnts, även klubbarna brukar har ngt. Dock bli dessa två alternativt sällan något man gör tillsammans som 2 pers och sedan är det ingen annan med.
Därför skulle jag hellre kolla på Kajakaffärer i din närhet (eller där ni vill vara) och fråga de. Många butiker erbjuder även kursverksamhet och det brukar sällan vara ett problem att tex bokar en kurs med samband till en tur eller så. Då ni planera utanför "högsäsong i kursverksamhet" borde det inte heller vara någon problem att det är fullbokad eller så.
Vet inte var ni bor men i Stockholm skulle jag t.ex kontakta Stockholm kajak eller Nynäskajak som båda två har riktig duktiga lärare.
Om Sverige ändå inte locka skulle jag kolla mot Åland. Har själv inte varit där än men naturen ska tydligen vara riktig fint med en härlig skärgård. Även där finns det kursverksamhet om jag inte missminner nu.