While I'm talking primarily about historical settings for this notion, it could probably work just as well in a lot of fantasy settings too. I can't claim credit for this notion (not that it's especially innovative in the first place), it was inspired by a section of Christan Cameron's Poseidon's Spear, where the protagonist took his ship and crew on a dangerous voyage, including overland bits.
People have done naval campaigns before, nothing new in that. But as far as I've seen, the fantasy standard is usually a sailing ship. Sailing vessels give long range, lots of cargo, and very few mouths to feed/men to pay, since you don't need an especially large crew to operate it (obviously when we get into gun decks with cannons things change once more to large crews). The core of this idea, however, is that the PCs and the game are centred upon a galley. While galleys do have sails, their primary motive power comes from muscle - as in men rowing oars. Oarsmen were sometimes slaves or otherwise oppressed men chained to their benches, but the best crews were free men, either citizen-rowers or professional mercenaries. This is an important distinction, because free men working for pay and a share of the profits aren't likely to kill the command crew should an opportune moment present itself.
You need a lot of men to row a ship, and if you can trust them with arms and armour, spending the time to train them to fight together, you're effectively a troop transport. A galley needs hundreds of men (the classic Greek trireme/trieres needed 180 rowers) who massively outnumber any marine/archer complement you might bring. If these are all combatants, you have a small army. An army with a means of getting around and a built-in organisation. The PCs would be the various officers on the ship, or if you wanted a troupe-style game, players could have multiple PCs (each playing an officer, a sailor, a marine, an oarsman, for example or some mixture of any two/three). The point is that they'd be in command of the vessel and thus the enterprise.
Obviously space is at a premium in a galley. So this would tend to assume your armed oarsmen aren't going to be heavy infantry, but skirmishers/light infantry. A helmet, a shield, possibly some light body armour and a javelin or three (perhaps including a heavier one that can double as a spear). This stuff all has to be stored somewhere, because you don't want to wear it while rowing, nor have it cluttering up needed space. If you could equip them all that way and spend time training them to fight as a cohesive formation and you've got a pretty potent little force.
There's a ready-made driving force for the game: hit the sealanes and make money. All those men need to be fed and paid. Taking other people's ships is an obvious source of income - not just the vessel and its cargo, but also potentially selling the crew into slavery and/or ransoming the more important people on board. Or offer the oarsmen employment (especially if they're slaves - freedom and employment is a pretty good offer) and you are building a fleet. There's another source of income - raiding towns on the seaboard. Again, you have an army, so anywhere small/lightly defended with a beach you can land on could be snapped up. If straight up piracy isn't palatable to the group, you could always go a more military route and have the ship be part of a more formal navy being sent about on special missions to advance the interests of a kingdom/republic to which everyone is part of.
The Mediterranean or somewhere like it (if not-historical) is an obvious place to set such a game, since it isn't as rough as the open ocean and has lots of settlements on the coast. People made a living doing this sort of thing for millenia. One of the reasons galleys worked was that there are lots of beaches; galleys aren't brilliantly seaworthy, they tend to stay in sight of land and need to be taken out of the water to dry out periodically; besides they are limited in how much water and food they can carry and have to stop regularly to re-supply. This might seem like a limitation, but it also keeps things relatively tied to the land, so it doesn't become a game of long stretches crossing blue water with little happening.
The when depends on taste. I like antiquity, you can go Classical around the time of the Greco-Persian Wars, for example, and be involved in the conflicts of the age. Or taking advantage of the concentrations of navies to pick off undefended places. In the Hellenistic era later you get ship-board artillery to play with and many rival contenders for Alexander's empire. In the Roman era you have the chaos caused by the Romans destroying the other naval powers of the world, then imploding into civil war. I'm sure there's plenty of later alternatives too, before you get into the Age of Sail and galleys disappear. Sound interesting to anyone?
How might this work in a fantasy setting (I'm thinking magic producing things like fireballs or messing with weather could have a significant impact on viability)?