To make exploration more interesting, I'd focus on spreading out the rewards of exploration over a longer period of time and making late-game rewards more appealing. The number one cause of exploration becoming less and less fun as the game goes on is that non-Pangaea maps are boring. Pangaea itself is a boring map that allows you to obtain most of the rewards of exploration in the early game. Nevertheless, Pangaea is still more fun than naval maps where you're cooped up early game because there's not enough land to explore. Not only is the game less fun in the early early game because you can't explore much, it's less fun in the late early game. Low exploration in the Ancient era usually means dark or normal age in the Classical era, which means you're missing out on the Monumentality golden age bonus. That slows down your game significantly, and you'll be spending even longer than otherwise before the game opens up and allows you to finally do the things you want to do.
One way to making naval maps more fun is to rework the whole golden/normal/dark age aspect of the game. Instead of rewarding players for entering golden ages and punishing them for failing to do so, different flavours should be available for different age types. Mutehsem Suleiman's bonuses (in the absence of normal age bonuses) are a good example of what I'd like to see. In a golden age, you're encouraged to develop your cities (+15% science & culture). In a normal or dark age, you're encouraged to flip the game on its head by taking what others have (+4 combat strength). There's a good enough balance between the two bonuses that it warrants a serious strategic consideration to decide what age type you should aim for in each era.
There should also be less emphasis on scouting as a way of getting era score and more emphasis on other methods. On a standard Pangaea map, with two scouts, you can feasibly get 5 points from tribal villages and meet 4 other players for a total of 9 points. Discover a natural wonder, and it's as high as 12 points. You'd be extremely lucky, however, if you can build two splendid districts in the ancient era for a total of 6 points. I don't really see why there has to be such huge discrepancy, given that scouting provides a lot of value outside of era score. It could also be interesting to have a system with multiple types of era score, and in order to unlock a specific type of bonus for the next era, the player needs to collect sufficient points of the corresponding type. For example, if you want bonus to science & culture per turn like golden-age Suleiman, you have to get "Development" era points by building districts and buildings. Defeat units and destroy barbarian camps and you get "Combat" era points and potentially unlock bonus towards combat in the next era. If you're able to get enough points for both, you get both bonuses (might be busted, but Civ 6 has heroic age, which is similar). You can also get points from scouting, but it'd be one of the following:
- There's a separate type of era score you can get for scouting
- You can get different types of era score for different scouting events
- Scouting yields "Wildcard" points, which can count toward whatever type of era score you want
Another thing that would make naval maps more appealing is to make maps bigger. The more tiles there are, the more land tiles there will be, and the more things to do even on a map like Small Continents. Right now, with two scouts, you can more or less map out your home continent in the ancient era on a Continents map. I'd like to see map sizes grow to at least make Continents, instead of Pangaea, the gold standard, so that there's still scouting to be done on the home continent beyond the ancient era. Obviously, there are some serious complications to increasing the map size. The game changes significantly even when you just play on a Highlands map instead of Pangaea. There are more barbarian problems, the AI tends to fight less because there's more land for everyone, and the map doesn't fill up even in the late game. There will have to be a lot of other adjustments for this to be possible. I can't find the post now, but I made a suggestion a while ago of implementing a pre-settlement era, allowing the settler unit to act as a walking city of sort and removing the scout unit and the first warrior. This unit wouldn't be able to move fast like the scout, which means the map doesn't actually need to be upscaled as much. Barbarians would make no sense in this context, so they'd be removed as well (they can appear later in the game after players have settled down). I actually like wild animals in this context, because they can actually fill the gap left by barbarians, but I don't want them to try to kill the player. Instead, the player can choose to attack the animals with the settler unit for rewards. Obviously, there'd be risk associated with this, as losing a battle could mean losing population. At the very least, though, you'll never be embroiled in unwanted combat at that stage of the game.
Last but not least, the naval game needs to be improved. Naval game is just too boring. On land, there are features that affect movement and combat strength. Aside from getting +3 strength on coral reef, there's nothing of the sort in the water. Land units can enter water. Naval units can't go on land or even cross land through a river. Making rivers navigable is something a lot of people have suggested. To make naval combat even more interesting, a wind system can be introduced. Each tile will have a wind direction attribute, and the movement cost of a boat depends on the wind direction and the direction the boat wants to move. I understand that it's the dynamic between wind and current that determines this in real life, but this is complicated enough for the game. I'm choosing wind over current because it can also affect ranged attack strength both on land and water. I'm on the fence about this idea, though, because I'm generally not fond of micromanaging units.
Another thing that could help is to make long-distance naval travel more expensive and exclusive to actual naval units (embarked units can only travel long distances when accompanied by naval units), but make the rewards that can be obtained through long-distance navigation bigger. After a certain amount of time out of friendly territory, naval units should slowly lose health. Technological development can mitigate this, and certain civs like Portugal could also have access to this bonus earlier. I haven't yet thought about what sort of bonus would be appropriate, though, but it should be something that would be hard to obtain on a Pangaea map.