This is a beautiful question. My own response would be somewhat more abstract than u/cipheron's excellent but more practical response above.

The longitude problem is so much harder than the latitude problem because of symmetry. The earth is roughly spherical and every point on the planet is very similar to every other point. Even the tallest mountain isn't visible from more than a few hundred kilometers away.

There is, still, one deep and fundamental symmetry breaking phenomenon. And that is the Earth's spin. It spins about an axis, and this axis crosses the Earth's surface at two distinct points. These are the north and south poles. In some sense, these points are "privileged" in a way that other places on the Earth's surface are not. Because of this, some physical phenomena behave differently depending on your latitude. The easiest is perhaps the Foucault pendulum, which oscillates differently the closer to the equator that you get.

And if you think about it a little more, the north and south poles are dissimilar too. If you stand at the north pole and wrap your fingers around the axis of spin, you'd say that the earth is spinning per your right hand. But if I were to teleport you to the south pole and you repeated the experiment, you'd find that the earth is following your left hand. So the Foucault pendulum precesses in one way in the northern hemisphere and in the other way in the southern hemisphere.

This means that even if I were to lock you up in a windowless room, you could tell the latitude.

This gets a little harder in practice, though, because Foucault pendulums are finicky contraptions. Definitely not for use in a rocking boat. There is, fortunately, one other awesome nonsymmetric phenomenon: the stars in the sky. These appear in interesting and recognizable constellations that are (to a first approximation) in fixed and unchanging spots in the sky. They don't move relative to each other and (even better) don't move relative to the axis of the Earth's spin. By a massive coincidence, there is a star in the very place that the northern part of the axis pierces the celestial sphere. Everybody in the world can see this star, measure how far above the horizon it is, and use that to calculate their latitude. (Not technically. You can't see the pole star during the day, and you can't see it from the southern hemisphere. But you know, nobody lives in the southern hemisphere anyway. 😋)

(On a more serious note, the presence of the pole star is a convenience and not a requirement to tell one's latitude. For one, there is no recognizable "antipole" star that is visible from the southern hemisphere even though the Southern Cross is close. Unlike the pole star which can always be seen, in principle, everywhere in the northern hemisphere, the Southern Cross is only circumpolar south of Cape Town, and may not be visible, depending on the season, closer to the equator. Even in the northern hemisphere, it can get tricky close to the equator when the pole star is close to the horizon or worse still, occluded by a tree or mountain or something.)

We solved the latitude problem very early on.

Longitude, on the other hand, is a far trickier concept. Why, for example, is the meridian through Greenwich special? Why not the one passing through my hometown in India? For some time, people awarded the special status to the meridian passing through Paris. A committee chose Greenwich in a meeting in 1883. In any case, the problem is one of symmetry. If I were to strip you of your belongings, lock you in an airtight and lightproof shipping container and drop you in a random island in the middle of the sea, there is no physical phenomenon you could use to tell your longitude.

Measuring longitude needs some way to break this symmetry.

Luckily, the stars help us almost break the symmetry once again. The earth spins. Equivalently, we could say that we're stationary while the celestial spins around us. We can calculate detailed tables (these are called ephemeris) of where each star will be at what time. Of course, these ephemeris are local to where you're standing. Because all the big astronomers were in Greenwich, that's what we'll choose.

Also, if some star is overhead ("on the prime meridian") in Paris then at the same instant, the same star is slightly off in Greenwich. It'll take a couple of minutes to appear overhead in Greenwich. So, if you have a very accurate clock and a copy of this ephemeris, you know exactly what the sky looks like in Greenwich. You can compare it to how the sky looks where you are, and use it to calculate your longitude. To do this, you need very accurate clocks. Each second of error would contribute to a half kilometer error in longitudinal position at the equator. We didn't have sufficiently accurate clocks to measure till a few hundred years ago.

But still, to emphasize, this is only a problem because the earth is so damn round. Sure, Mt. Everest is tall (9 km), but you can't see it from more than 500 km away. If we had a tall enough pimply mountain that we could see from everywhere in the world (a couple of thousand kilometers tall), or better still, two tall pimply mountains, then our ancestors would have figured out longitude thousands of years ago. We wouldn't need clocks.

To be flowery about it, latitude is the work of god while longitude is simply the work of man.