Have you tried messing around with the settings in the Nvidia Control Panel??
The game supports 800x600, 1024x768 and 1280x1024 resolutions with either 16bit or 32bit colors. (Thanks Petrell!)

Have you tried playing in windowed mode?
And whay exactly mean you can't get any resolutions to work? The game doesn't start/crash or is it something else?

I eventually managed to get 800x600 to work through some combination of changes in the Nvidia control panel. No luck on the others, but as long as it's working then it's not a super immediate concern.
Higher resolution would be nice, but I'm willing to take what I can get. :)
At install, the game loads a graphics card test app to find compatible resolutions. I tested each available one in order and each one failed, which then make it impossible to boot the game.
Things seem more or less sorted now, though I have no idea why.

Do you have problems with the game itself or is it just that during the graphics setup test you can't see the test image?
If you're getting a "The resolution cannot be initialized" error, try this solution. It talks about 800*600, but if you have this exact problem, you could give it a try.
If you can't get it right even with this (and even after eventually contacting GOG support directly), and would like a very similar game, buy Port Royale 2. Almost the same gameplay (a tad bit easier IMO), and a vastly different environment.
(Heck, if your finances allow, I'd say get it even if you can get Patrician 3 to work. They are both great games, I'm enjoying them both at the same time ;-).)
EDIT: Oh, I see you've got it to work more or less already. I still think you should check that support page I linked out, though.

The a solution was posted here:
http://www.gog.com/en/forum/patrician/will_not_launch/_/3

Make sure your Hz isn't 70 or above, i think that is what makes it break
So change it in the Nvidia Control Panel