Solved at last!
The destination is (aptly, given the setting):
THE SOUTH SANDWICH ISLANDS - one of the world's remotest island groups.
Solution path (brace yourselves - it's a biggie...):
First, let's do the obvious thing here and identify all of the flags in the image. Note here that each column contains 7 flags (of countries, territories, island groups, states, counties, cities, and even one nautical signal flag); each one has been halved and both halves appear in the same column.
NB The white cross on red background is not Denmark - as you'll see later, we need the Sovereign Military Order of Malta as part of our solution...
Here, the rows in white are the top halves, while those coloured blue are the bottom halves.
Side note for OP (because I know you'll want to know...): It took me about 2 hours to nail down this list! Most of the national flags I could do from memory, but I had to cross-reference Wikipedia (and other) lists of flags for US states, UK counties, flags with the Union Jack on them, flags by colour combination and triband flags. Afterwards, there were still some I couldn't pinpoint this way, so I had to zoom in on details in the image like words in mottos on crests or unusual pictures within the flag and Google for those (hit and miss). Finally, I only had to reverse image search 4 flags as nothing else was turning up the answer (Ceuta, Chatham Islands, Dortmund and Tierra Del Fuego).
The most crucial thing to notice here is that:
Each row contains either all-top-halves of flags or all-bottom-halves. In fact, each row can be paired with one other so that all flag halves match across the two to form a set of complete flags. This is going to be useful later...
Let's turn away from the flags for a moment and focus on the message in binary. There are (at least) four clues in the text as to how to decode this:
1. If you take the first letter of each line spoken by Pat, this spells out VARICODE.
2. When Pat says she'll have 'the Pastrami Special on Kaiser, with the 31 seasoning', this is a cloaked reference to PSK31.
3. Pat mentions that she loves the Ham on Rye.
4. Pat also mentions a 'radio ad'.
What is this leading us towards?
The world of ham radio (a colloquial name for amateur radio). From the linked Wikipedia article, PSK31 (or 'Phase Shift Keying, 31 Baud') is a "computer-sound card-generated radioteletype mode, used primarily by amateur radio operators to conduct real-time keyboard-to-keyboard chat". Varicode is the code used within this to encrypt each character, with full support for ASCII and all the main symbols you might wish to encrypt.
Most importantly for our purposes:
The binary message is actually encoded in Varicode. In this system, the string "1011101101" which appears at the start of the message means "START OF TEXT", and the string "1101110111" which appears at the end of the message means "END OF TEXT". Every occurrence of '00' marks a space between different characters. We can then decode the binary appearing between each of these spaces using the Varicode system to find the message (though I had to do this manually, as I could not find an online decoder without having to download files through GitHub).
The message then translates to the following:
[START OF TEXT]
DE [SPACE] AA3PAT [RETURN]
QSO [RETURN]
GJ1O [RETURN]
A53R [RETURN]
ZD93A [RETURN]
1A04B [RETURN]
J491L [RETURN]
OY5I [RETURN]
VK9N2U [RETURN]
OX3K [RETURN]
GD2A [RETURN]
J22N [RETURN]
KL71V [RETURN]
CU2E [RETURN]
KP43I [RETURN]
A21S
[END OF TEXT]
With a little knowledge, there are a few things we can note about this message:
This bears the hallmarks of a ham radio transmission. There are a few specific codes used in ham radio which we can spot at the very top:
"DE" means 'from'.
"AA3PAT" is the call sign of the station transmitting the signal. "AA" implies that this station is in North America. The "3" immediately following it shows that it is specifically within an area in the West of the USA or Canada. 'PAT' is a unique code specific to the broadcaster. Thus 'AA3PAT' here signifies that this transmission is from agent Pat, who is based in the AA3 region of North America:
Source: mapability.com
"QSO" is a standard 3-letter Q-code used in amateur radio communications, specifically to signify one station making contact with another. It is normal to find it at the start of a message, as here.
What this then leaves us with is:
A set of 14 codes between "QSO" and [END OF TEXT], each of which looks like it might be in the format of a radio station's call sign.
In particular, it's notable that the first part of each of the 14 call signs listed relates to a country or territory whose flag appears in the image (using this list):
GJ1O: GJ = Jersey (col 6, rows 4&6) - remaining 1O;
A53R: A5 = Bhutan (col 5, rows 7&10) - remaining 3R;
ZD93A: ZD9 = Tristan Da Cunha (col 9, rows 3&8) - remaining 3A;
1A04B: 1A0 = Sovereign Military Order of Malta (col 3, rows 7&10) - remaining 4B;
J491L: J4 = Crete (col 10, rows 1&14) - remaining 1L;
OY5I: OY = Faroe Islands (col 9, rows 5&11) - remaining 5I;
VK9N2U: VK9N = Norfolk Islands (col 11, rows 3&8) - remaining 2U;
OX3K: OX = Greenland (col 12, rows 9&12) - remaining 3K;
GD2A: GD = Isle of Man (col 1, rows 9&12) - remaining 2A;
J22N: J2 = Djibouti (col 1, rows 2&13) - remaining 2N;
KL71V: KL7 = Alaska (col 3, rows 1&14) - remaining 1V;
CU2E: CU = Azores (col 7, rows 3&8) - remaining 2E;
KP43I: KP4 = Puerto Rico (col 5, rows 1&14) - remaining 3I;
A21S: A2 = Botswana (col 12, rows 4&6) - remaining 1S.
What next? Well note that...
...there are not only 14 call signs in this list but also 14 rows in the flag image. Let's do a few steps at once here:
1. Match up each call sign in order to the corresponding row in the flag diagram (i.e. the first call sign, GJ1O, to the first row of half-flags; the second call sign, A53R, to the second, etc.);
2. Pair up the rows of the flag image to form the complete flags again (keeping the call signs matched to the rows as they move);
3. Then consider just the so far unused portions of the call signs, i.e. the final number-character pair. It is possible to arrange the rows of flags in such a way that the number parts of these pairs are put in increasing order and the letters beside them then spell out a phrase!
Reading down the characters at the far right of the diagram, we can see the phrase SOLVE A NURIKABI - so now we need to treat our image as a Nurikabe grid!
How do we do this? Perhaps the natural thing to do is:
to use the squares containing countries that were indicated among the list of call signs (highlighted orange in the diagram above) as those where we need to place the starting numbers.
What numbers do we use? Well, why not try using the numbers from the middle part of their call signs (thus far only used for ordering the letters to give the message in the previous step) - the starting grid would then look like this:
Following the usual deductive steps for this kind of puzzle, we end up at the following state:
So now what?! Well, squint and you might be able to make out...
...that the black squares appear to take the form of the number 3166. What's the significance of this? Well, this is surely a nod towards the ISO 3166 specification of alphanumeric country codes and sub-codes! The OP therefore expects us to convert some or all of the countries in the grid to one of their ISO 3166 codes, and then perform some further translation of some kind to perceive the next part of the message.
A message of sorts emerges if we specifically use the ISO 3166-1 alpha-2 2-letter codes for the geographical entities in the unshaded spaces (and not already replaced by a number for the nurikabe) of the diagram above. Using these codes, reading along and down the rows yields the letters NO/SH/AS/IN/SI/LI/CA/KI/CK/SH/AW/BO/TT/OM/ME/AT/MU/NI/CH. While this can potentially be parsed into several different phrases, the one we want (after a little trial and error) is:
NOSH AS IN SILICA KICKSHAW BOTTOM ME AT MUNICH.
Coupled with the OP's hint in comments below that we might find it helpful to add '(8)' to the end of this phrase, this suggests the enumeration of a cryptic crossword clue (something which forms the basis of many of the OP's other puzzles...).
So let's solve this final step of the puzzle...
'NOSH', here, is the definition - the answer will be a foodstuff.
'AS IN' is the connecting phrase between the definition and the wordplay.
'SILICA' is SAND...
'KICKSHAW BOTTOM' is W - the last ('bottom') letter of 'kickshaw'...
'ME AT MUNICH' is ICH - the German word for 'I' ('me').
So this cryptic clue yields up the answer SANDWICH - which is particularly appropriate given all the talk of sandwich fillings between the two characters in the flavour text!
For complete closure, where is the geographical location in question? After all, there are a few places in the world with this in the name. Well, there were a couple of pointers in the puzzle:
In the dialogue, Pat says "We're going island hopping south of the equator this time!" So we're looking for somewhere south of the equator (which rules out Hawaii, which was once christened 'The Sandwich Islands' by James Cook) and we're also looking to go island-hopping, suggesting more than one island by this name (which rules out Manuae and Efate, both previously known as 'Sandwich Island' to James Cook - boy, did that guy love a sandwich...).
This leads us to the territory of South Georgia and the South Sandwich Islands, which ticks all the boxes! And - wait for it - was also named by James Cook. Someone buy that guy some lunch already!
