You'll need a full-bodied red. Ouzel's suggestion of a 'reserva' Rioja is a good one, as the minimum of one year's ageing in oak barrels gives it plenty of 'clout'. (If you want something almost chewy, go for a 'gran reserva', which has been aged for at least 2 years on oak barrels).
However if you want flavour to come from the grapes, more than from the oak, it's hard to beat a really good claret. Look for a 'premier cru' St Emilion . A 2005 vintage won't come cheap (because it was probably the best year for quality Bordeaux wines for a couple of decades) but it will shout 'quality' at you.
Chris