Here's an idea I had a while ago, reposting here - bolded language is most pertinent to this discussion:
No more rule that you can't explore ocean tiles until astronomy. Rather, you can go onto ocean tiles, but every time you pass through an ocean tile (not each turn, but each tile), you take X amount of damage, similar to how Carthage ends on mountains. And it would be a fixed amount of damage, meaning that as you increase in technology and your boats get stronger, they take the same amount of damage, but have a higher strength so they can withstand more.
This makes things much more interesting, IMO, and makes naval exploration actually much more fun. You now can take your boats to the edge of the coast and venture into the ocean, not knowing how many turns it will take for them to find new lands and end the damage. If you head off the coast of Portugal thinking its only 5 tiles to the New World, and you're right, you will get there early. If not, you'll die, and you'll need to improve your ships capabilities until they can make the voyage. The only limit is your sense of adventure and risk-taking.
This system would also allow more SP experimentation in the exploration tree. Maybe a policy which cuts down on the damage taken per tile. Maybe a policy for increasing the sight specifically in oceans. Great admirals would have special skills relating to crossing ocean tiles or seeing inland from ocean tiles. Maybe a policy unlocking a unique unit, a scoutship, which has double movement in ocean tiles. I don't know, just spitballing.
This system would also play into the trade routes system. It seems insane to me that there's no overlap between exploration and trade routes, since the whole reason Europeans embarked on exploration was to open up trade routes. Maybe there should be a rule that trade units can't cross ocean tiles at all until either technology X or you pick the right social policy (and the SP would come long before the required tech, making it really worth it). This would basically make inter-contintental trade routes impossible unless you were an exploring nation, which is both historically correct and adds a big boost to the gameplay aspect of exploration.
This actually ties into a much more basic idea I have that all units should always take damage when outside friendly territory.Period. And that amount of damage should be proportional to the number of tiles that unit is from a friendly tile (calculated in the shortest possible line), which would represent supply lines. This basic idea would make exploration much more useful as a social policy, but also really make the world 'smaller' until later in the game, as it should be. I shouldn't have good knowledge of the world until the 17th century.
Sounds more fun to me, at least, and I think could be implemented with very few changes to the basic code of the game.