For REAL flamenco, not the tourist stuff, there is only one place I recommend in the city: La Solea. Check "La Guia de Ocio"("Liesure Guide," available at any magazine kiosk) for address, times and so forth. Get there around 11 or 12, if on a weekend, no later, because it will be packed. You will hear real flamenco, the singers and guitarrists are not paid, just afecionados who really love the art. Sometimes a dancer will make an appearance. This is the real thing! Trust me, I used to play flamenco guitar professionally, and my thesis in Anthropology at the University of Kansas was on Spanish Gypsies and Flamenco.
¡Disfrutas!
Martín