I've got a message to GOG already sent, but I wanted to still pose this question.
I can't get the game to launch. I get the following message dialog that pops up in a box when I try to launch:
"Patrician 3: The resolution (800x600x16) could not be initialised. Please install the latest driver for your video card and then start the "P2Setup.exe" program."
I admit I haven't tried to update the graphic card driver, primarily because the game is older than the card. I also had run the test box repeatedly and tried to set the resolution to the max, but I still get this dialog box no matter what I do. Once you click "OK" the box closes and that's all that happens. It's very frustrating.
I can find no other setup options or other things I can change.
Thanks for any ideas.

Have you tried the graphic card test from game folder in start menu (Start -> programs -> gog.com -> patrician 3)? Does is pass any test?
What are your system specs?

Well, you should always try updating the drivers, but I have a question.
Are you running the game on a laptop? If so, what card / chipset is it? Apparently, the original Patrician 3 was not supported on many laptops, and the developer was clear that this was because of the limited number of graphics chipsets laptops generally have. I do not know if this has since been fixed, but it was a known issue at the time.
And it resulted in the same thing you're described, an error message about not being able to initialise the graphics.
EDIT: Okay, I found this information on Direct2Drive's pages for the game:
"Known Issues: Laptops are not supported" - so it seems it applies to the current version of Patrician 3 as well.

Yes, the only one that passed is the highest resolution "1280x1024x32" and I press OK and that box disappears but it's not seeming to matter.
Spec is as follows:
AMD 64 3800+ MMX 2.4GHz
3582MB RAM
7600 GS NVidia Integrated
Windows XP 5.1
DirectX 9.0c
It is a desktop.
I am going to work on the video driver to be sure.

Does you graphic card support 800x600 mode on desktop (right click desktop -> choose properties -> properties -> resolution [might be bit different names as I'm translating from my language]). What is the smallest resolution that slider allows? The problem probably is that the game menu require the 800x600 resolution.
If all else fail I could go try the game on my parents computer as I has 7600 GS 256MB AGP card (non integrated).

I updated the video driver and still won't run. After updating, none of the video resolutions show me a picture, so nothing passes the set-up test now!. I wonder now how I ever saw that boat when I frst ran the program the first time.
Also, I tried setting the native resolution to 800x600x16 and still won't run. I'm still stumped.

So you can set desktop to 800x600 res? If so I'm out of ideas :( I'm currently looking in various places hoping to find an aswer.

Are you running a dual monitor setup and/or are you using a widescreen monitor?

I have a similar problem.
My Vista fails the 800x600 tests, but passes the higher resolutions. The game still wants to start in 800x600 it seems and gives me this error:
"---------------------------
Patrician 3
---------------------------
Patrician 3: The resolution (800x600x16) could not be initialised. Please install the latest driver for your video card and then start the "P2Setup.exe" program.
---------------------------
OK
---------------------------
"
edit: messing around with desktop resolution and installing the latest nvidia drivers did not seem to influence the error or the graphics card test.

Is there an .ini file in the games folder that will allow you to set resolution changes?

there is a configuration file "P2.cfg" but it's in german
[SPIELEINST]
VORNAME=*removed*
NAME=*removed*
STARTJAHR=1300
GESCHLECHT=0
SCHWIERIGKEIT=0
ZIEL=0
LAUFZEIT=0
STADT=15
PRODUKTION=1
DETAILS=1|1|1|1|1|1|1|1
[OPTIONS]
ZEIT=5
DETAILS=3
LSMUSIK=22
LSSOUND=127
LSVIDEO=68
VIDEOS=1
TOOLTIPS=1
FARBTIEFE=1
AUFLOESUNG=2
SWAPSPEAKER=0
ORLOGONLY=1
WEATHER=3
AUTOSAVE=5
[BRIEFEINST]
OPTIONEN=0|0|0|0|0|0|0|0
SOUND=27

Checked it through a rough translator it doesn't appear to have anything about resolutions unless LSVIDEO=68 is it. No Idea what that 68 means though, you could try 80, in the hope that means 800x600 where 68= 680x480 but it is purely a guess.

I'm not the one having trouble so it's useless for me to mess around. One of them could post theirs to see difference. Also game does not support below 800x600 resoution either.
Game supports 800x600, 1024x768 and 1280x1024 resolutions with either 16bit or 32bit colors but the menus are 800x600 res.

try manually setting your desktop rez to 800x600 and then launching it. This worked for me.

In that case I don't have a clue what LSVIDEO=68 means.