To answer your two questions in backwards order, but easier context:
Scene Framing
Splitting the party is easy and fun when you don't let scenes drag. Just as much as movies and TV cuts to relevant points, you should aim to start scenes as close to the important action as possible. Don't spend long on the set up, get to the interesting point of the scene ASAP. Throw clues in their faces. Put hard choices there too. And, cut away quickly too. Scenes should be 5-10 minutes at most. Since we're not talking high crunchy combat scenes, cutting away is very easy to to do here.
Known, Sought, Given Information
So, you're doing an investigation adventure, right? Go watch some investigation shows, read a few books. What happens in these stories? There is NO WAY for the protagonist to NEVER get the clues, it's really only a question of how they get the clues, how beat up they get along the way, and whether the clues come in time to do something about it or not. (Usual Suspects is a great movie example of getting all the clues too late.)
Information comes in 3 ways:
Known
Known information deals with things the characters ALREADY know. This can be inferred from their skills, their classes, backgrounds, history, etc. "You were a galley slave before being a pirate, you recognize the scars on the ankles from chains anywhere..."
Use this give each character plenty of context, plenty of "read" on characters or objects. ("He walks with a swagger, not the kind that comes with hardship, the kind that comes with having lived one's entire life at the top. You can see the difference anywhere. He's not one of you.")
Known information should often include lots of free clues or reads on things, because it gives players a feeling of expertise and competency for the characters. You can have dice rolls or whatever about specific questions or further clues, but start with the info their character can JUST SEE from the start.
Sought
Sought information has to be... sought out. This means it's not immediately obvious and either has to be collected ("pickpocket the letter tube from his bag"), or "processed" in some manner ("Scraping the iron shows it to be a softer type than normal. This was a cheap replacement, not the original.").
This is where character skills and player choices can be made, but since few players think of their characters as investigative types, you will want to provide some suggestions along the way. ("You've traveled far from home, but you're the best one on the ship when it comes to recognizing foreign plants. Maybe if you got a look into the doctor's herb bag you'd know what's in there...")
Also recognize that while a social character can con, trick, pressure characters into revealing information, the quiet high-perception character can often read other things about someone without directly interacting with them. Consider that a potential parallel method as well.
My suggestion is that if you have any kind of sought information available, make it something the players acquire/understand with just one skill check/dice roll/etc. Failure shouldn't mean "you don't learn anything" but it might mean "You get caught trying to get this", "The evidence gets destroyed/lost", "You only figure out what it means too late" etc.
Given
Here's a thing few rpgs get from investigative stories - a lot of clues just FALL into the protagonists' laps. People spill the beans, come forward, tell the dirt on someone else to get them in trouble, the heroes just happen to luckily be at the right place to overhear some incriminating statements, they stumble upon a crucial clue left forgotten at a crime scene... this stuff happens a lot. The only reason other media gets away with it is that the heroes often suffer so much it's like "well, sometimes you gotta get lucky, right?".
One of the better rpgs to deal with investigation is Dogs in the Vineyard, which has a pretty simple bit of advice - have several characters try to GIVE the information straight to the PCs... lying or omitting just enough to cover their own asses or their friends. The other bit of advice is that straight out lying should have the GM say to the players, "You can tell they're lying, you're just not sure what the real truth is."
AS long as everyone is at least looking for information, one of these three types should be available to give clues or at least ideas on how the characters treat/feel about each other.