edit: I am asking for help, and maybe I should be more greatful, but I can not see the game that went so far away from anything i ecpected as a railroad game seson... again, not one thing went as planed, and everyone hated it. Normaly they throw me a curve or two but I can guess how they will react to most things, and when things go left in one place we find things from there continue fine.
My advices :
1. Have your PCs meet
recurring friendly NPCs (plenty), neutral NPCs (many), and hostile/cheating NPCs (a few). This way, the players will have reliable sources of informations, that you can use to tell them what you want them to know. Paranoid players are, after all, only all too well adapted players. Too many DMs forget that foes and threats are best used as exceptions. Moreover, Paranoid players are not that predictable, after all paranoia is a mental illness...
2.
Work a lot to create the atmosphere : prepare hand-outs to point toward what is important, be very specific on what is to be considered important in the
read-alouds that set the mood of a scene. Insist on what is often forgotten : colours, odors, ear rings, tatoos, etc. You can create a link between a PC and any NPC by giving them both the same tatoo, the same accent, the same cloth style, whatever... Every hint will be heard and used (even unconscienly) by the players. Create as many links between the PC and the NPC.
3. React with skill tests on every PC reaction to he scene. But prepare beforehand a few "punch lines" that wll give some textures to the informations you give them through Perception, Insight, Streetwise, History, Nature tests (try to vary the tests to force all the players to react and state their mind... To know what they have in mind and how they percieve the scene). Throw a few heroes of the past names, titles of legendary books, name of places both legendary and genuinely located in their world. And reuse them as often as possible. They should percieve your information as sound, not Ad-Hoc info that is thrown on the spot. Even when the skill tests are failed, give them information, only much broader and much less acurate, but rarely false.
I found it immensely helpful to use
Masterplan and to set in most of my encounters one or two skill challenges.
They force me to write down the goals of the encounters, a few hints with a believable guise and to prepare for a B plan, if the challenge is a failure. It gives me a frame to prepare the session. Better still, I have 6 players at my table at the moment, so if I ask each of them what they do in turn, I have most likely a complexity 1 skill challenge completed... I never tell them they are in a skill challenge, but it helps me to force them to state their mind. And it gives me some milestones to feed them with more information that doesn't seem railroaded, because I most likely give new informations that derive directly from their actions in my (invisible) skill challenge.
On a final note, railroading is not evil... Unless the players notice it. I think you did not provide your players with enough hints, and the hints given where too "thin" and did not seem striking enough, to me at least.