What is the smallest heatsink I should get that works well.. I don't want to have to use a huge case or anything.

Well many people use computer heatsinks. I myself used a couple Radioshack heatsinks on each chip, although I don't think it's enough, I may have to add a fan. But the Radioshack heatsinks are smaller I think, although the computer heatsinks would work better.

I'm using a modified heatsink from a PS2. Its long, but its only .5" thick.

I got 4 heatsinks from allelectronics.com (part number HS-56), for my 64 portable, they get a little bit hotter than the original heatsink but work fine as far as I can tell. The chips on the 64 are tested to high temperatures, but if they get too hot it could reduce the life of the 64 chip.

The ones at allelectronics.com is what i use, but I pulled them off some old intel dx's.

Hey those allelectronic ones are cheap! Thanks! BTW, when I get them, do I just glue them on or what?

You can use superglue but I'd suggest putting some kind of heatsink grease between the chip and the heatsink because then more heat will be transferred.

I'd use thermal adhesive. Its like a glue version of thermal grease.

Where can you get that thermal adhesive? The way I was going to attach the heatsinks is to use the sticky pads already on the 64 and glue each corner of the heatsink down. By the way, you'll have to cut the heatsinks to fit. I used my dremel tool.

hmm... your ideas not too bad actually. I want a more secure way to put my heatsinks on though since they'll be upside down in the case. It'd be horrible if they fell off and shorted something.
Anyways, I found some at my local radio shack once, but that was a long time ago. Here is a place that sells tubes of the stuff. They even give a warning about how if you use this, its on forever, almost at least...

When I made my P64 I just filed down the heat sink (verticly) and bent the big useless parts until they broke off.

i am using heatsinks form some old graphics chips(intel's or somthing "stolen" w/permission from non-used school pc's) pretty small but get hot with prolonged play so i will have a fan in mine.

that was me up there ^^ sry