The Bink video plays just fine, I get the loading screen and hit "New Game". The resolution switches and the game crashes to desktop. Here is data from the event log:

Faulting application name: oc3.exe, version: 0.0.0.0, time stamp: 0x391aa5ae
Faulting module name: oc3.exe, version: 0.0.0.0, time stamp: 0x391aa5ae
Exception code: 0xc0000005
Fault offset: 0x00557868
Faulting process id: 0xe10
Faulting application start time: 0x01ce501d93252b27
Faulting application path: C:\Program Files (x86)\GOG.com\Outcast\oc3.exe
Faulting module path: C:\Program Files (x86)\GOG.com\Outcast\oc3.exe
Report Id: d51154bf-bc10-11e2-be90-e811322330ae
Faulting package full name:
Faulting package-relative application ID:

I've tried running as admin and XP SP3 compatibility mode.
Any ideas?

Maybe your graphics card can't handle the weird resolution that the game uses: 512x384. You could try poking around in your scaling options, but it might be easier to try the fan-made high res patch from the sticky thread in this forum. That will let you increase the resolution to something your card can put out.

Check the sticky about the experimental patch at the top of this subforum, if you haven't already.
It can be a nightmare to run Outcast properly on modern systems, but the fanpatch works quite well for me.