Cheese
Cheddars and similar sharp "English" cheeses: Dry reds, Cabernet Sauvignon or better Merlots.
Swiss, Gruyere, and the equivalent: Pinot Noir.
Blue cheeses: Sauternes (or other sweet, fine dessert wines) is traditional, but these also work nicely with dry reds, and surprisingly so with very dry (Fino) Sherries. Be careful about tannic reds like Cabernets, though, which sometimes get a funny metallic taste with blue cheese.
Ripe, creamy cheeses like Camembert and Brie: Rich, buttery Chardonnay. Or for a change of pace, try them with Champagne.
Hard cheeses like Parmigiano Reggiano, Romano, etc.: This is probably kind of a cliche, but I really do like them with dry Italian reds, from Chianti to Barolo. Or try a chunk of really fresh Reggiano with a heavy Amarone.
Pairing Wines With Food