"And by international law, all that was ceded was the fortress and a small, town. If you want to apply that, sure, go ahead: Gibraltar would have no airport, no rights to expand their holdings into the sea and no territorial waters. And the United Nations clearly considers Gibraltar colonized territory; that isn't a rosy picture."
You're making too much out of the dispute over the isthmus. It's a very tiny part of what already is a very tiny territory. The vast majority of Gibraltar was undoubtedly ceded, and the isthmus would have been too if there were fortifications there, which is plausible. Saying they only ceded a fortress and small town still means they ceded all of Gibraltar besides the little neck of land where the airport now is, assuming that area wasn't covered originally. This is a strong argument by Spain since it looks like Britain didn't enforce control of the whole disputed isthmus till the nineteenth century, but we'd have to look much more into the issue to give a definitive answer. Were there fortifications there? Did Spain consider the isthmus part of Gibraltar when the treaty was signed? Did Britain? And so on.
As for territorial water rights, it seems strange to me that a territory ceded because of its strategic naval position wouldn't include the adjacent waters. That would require more research than I'm willing to put in right now, however. At any rate, the United Kingdom only claims the territorial water limits which were customary at the time, not the expanded modern ones or an EEZ, so if anything it's keeping to the customary international law as it existed when the treaty was signed and not taking advantage of rights it probably could claim today.
As for the UN considering it a colonized area, the United Nations list of Non-Self-Governing Territories is a joke these days and everyone with cursory knowledge of it can see so. For example, it still lists Bermuda on it, even though Bermuda runs everything for itself besides defense and much of diplomacy. Gibraltar has a fairly similar level of self-rule. It also includes teeny territories which could never survive as independent states and whose inhabitants do not want independence, like the Pitcairn islands and Tokelau. The list also excludes such obvious genuine cases of non-self-governing territories such as the Palestinian territories. The list is nothing more than a relic of the mid-20th century decolonization movement that has outlived its relevance.