One of my favorite things to do with tiny fleets of miniature ships is play map-based mini-campaigns with limited intelligence. The idea is to give each player a squadron, and let them grope blindly around the seas searching for each other until they stumble into a battle. Players on the same side are allowed to communicate only via written messages, and are told only what they can see from their own squadrons. The referee (me) has a master map and passes the written communications (sometimes with delays) and observations to the players, and sets up any encounters between enemy ships. Watching players struggle to coordinate their actions and bring an enemy to battle on favorable terms is a hoot, and the lopsided scenarios that result are fun because there's a larger strategic context giving the players motives beyond "win this battle".
The GQ 2 rulebook contains rules for running such campaigns, but these are too detailed for a referee to realistically manage at a reasonable game pace, and there's no useful map. In 2000 I discovered the Great War at Sea series of games by Avalanche Press. These have beautiful, full-color maps of the theater of war, gridded into 32-mile sea zones, and gorgeous color counters to use for marking the locations of rival fleets. The GWaS rules could even be used as written to run the campaigns, but if I'm running these games at conventions with players who may only play once and need to learn the rules in 10 minutes or less, I prefer to use my own, simpler rules.To use these rules, I have some props.
For the referee:
For each player:
The players write down their moves and hand them to the referee. The referee examines all the written orders and determines where and when fleets encounter each other, and adjudicates the results (declaring a battle when necessary). In the meantime, players are free to send messages to each other.
Multi-player games almost invariably have plenty of coordination issues without any interference from the scenario or referee, but just for fun I usually introduce a few more. My intelligence briefings usually contain some inaccuracies about enemy dispositions. Sometimes I say a dreadnought or battlecruiser has been completed, refit or repaired sooner than expected, sometimes an important ship or two is missing because of a non-battle problems (mine damage, machinery breakdowns, refit, etc.), sometimes a ship starts the campaign at less than full strength (if it's machinery needs overhauling or it's not fully repaired since the last battle), etc.
I also give each player individual victory conditions which don't quite align with those of the other players. Getting players to follow their victory conditions can be a challenge.