I decided that I wanted it to be 20x20 to give enough detail but not have too many paint swatches (that's already 400 paint swatches).
I found a picture of Hugh Laurie from the show House online, brought it into Photoshop and reduced it to 20x20 pixels. Play around with the Image Interpolation Mode (under Preferences/General) to see which one works best in preserving the right details when you reduce it. Then I enlarged it to fill a piece of 8.5"x11" paper and made a grid between each of the pixels.
I printed it out and took it to Home Depot to pick out Martha Stewart Living paint swatches. They are twice as tall as they are wide, so I cut them in half to make squares (I believe they ended up being about 1.5"x1.5"). You can use any brand of paint swatches you want, but all of the other ones at Home Depot don't have nice even proportions, so you'll end up with a lot of waste trying to cut them square.
I used 3M Super 77 to attach them to a pine board. Remember to spray lightly so that the paper doesn't buckle or bleed through. I used Gorilla Glue to attach a piece of wire to the back of the board so that it will hang on a wall.
When you're done, take a picture, upload it here, then give it to someone you love.