Yeah, the videos are pretty vital to the storyline and such, so you'd be missing out on a lot without them.
The videos are actually bink files, which is a video format that's used in quite a lot of games and also outside of games. As far as I'm aware your graphics card is used while rendering them, so outdated drivers and such could cause your problem.
So, before anything else, get the latest drivers for your graphics card. If you have an Nvidia or ATI card, there will almost certainly be a newer version than those which came with it available on their official websites (www.nvidia.com
If drivers aren't the problem, although it is likely, then I'm afraid your only other option is to post on the official Psychonauts technical support forum. Although this issue was reported a while ago, it hasn't been reported since 1.04 came out so perhaps they think it's fixed. Naturally, they will soon realise this is not so if you post a fresh complaint of the issue!