Are you looking for a single adventure, a multi-episode arc, or a campaign?
Are the adventures set in present-day, a historical holodeck scenario, or other combination of past/present?
One possibility of past/present would be to find historical records and/or evidence that leads the characters on a larger adventure ... a blend of the stronger elements of 'Time's Arrow' and 'The Search', possibly.
Another possibility, though perhaps a bit stock, is to have a Q transplant crewmembers from a starship to a sailing ship. Ultimately, they're not doing anything differently, though they seem to be - it is only that Q has put things, '... into terms your human minds can comprehend.'
A first contact mission could become a pirate-era setting if that's where the culture happens to be. Your characters could be tasked to find the advance team, but is unable to locate them by communicator, etc. A survey of the post reveals that it's been blasted apart by what appears to be cannon fire. So the only way to find the advance team and rescue them ... is to become pirates yourselves.
Bob