ignoring Tapas for now, paella is what i am craving so which restaurant in Madrid has the best paella? also what other mardilean typical food should i try? (again ignoring tapas which i'll be eating anyway)

Uff! I don't know about the best paella in town....if I leave out my mother's out of the competition that is!!! (and my own veggie one :o )
And, I confess I've only been to the famous (specially amongst 'guiris') Champagnería/Arroceria Gala www.paellas-gala.com once (it happens when you live a couple of minutes from a place), and wasn't at all impressed by their food. Of course we ordered some quite non-conventional dishes such as "fideua mixta", "paella oriental", etc... so I really can't tell you if they master the more classic stuff such as paella and arroz a banda....

Well, while paella is definitely NOT a Madrilenian dish, 'Callos a la madrileña' o 'Cocido Madrileño' are....

Personally I don't like callos, which are tripe :p , but see some ideas for cocido places on this recent post:
http://www.madridman.com/ubb/ultimatebb.php?ubb=get_topic;f=4;t=001049

Other dishes I wouldn't miss would be a nice Fabada, Gazpacho, Bacalao al pil-pil or a la Vizcaína, Pisto, Migas, Menestra de verduras, Pollo al ajillo or a la chilindrón, Caldereta....

I've been to the paella place mentioned above and whilst it definitely is a guiri haven (I was taken there by my company whilst I was trying to decide whether or not I wanted to move to Madrid), I found the paellas quite tasty. I think it is worth a visit, but remember to book if you want to be seated in the nice indoor gardem out back. Otherpaellas I've had here have been pretty hit and miss. Thursday is paella day in most cafes and really it does de`pend on your luck. Look for the very non-touristy places (typical cafes and local food place) that are busy on a Thursday.

Other foods i've really taken a liking to are Rabo de Toro (Ox tail), Lentejas (lentils), Calamare (squid), pulpo (octopus) and butifaras (catalan sausages).

At this time of year there are a couple of dishes you should try (not typically Madrileno but available in many places):
Pote Gallego -- a delicious Gallegan soup.
Fabada Asturiana - an extremely famous bean stew from Asturias.
I believe there is also a bean stew called Albuias a Pinto which is very filling...
Also please try Morcilla as a tapa or pincho!

PS If you want a good steak, there are some excellent Argentinian restauarants to try from,

thanks, i'm getting hungry reading all the recomendations. i'll definitely try the tripe, i would love to taste how the Spaniards make it, we make it with beans in my country (Jamaica) and it's so good, definitely will be trying the other dishes as well. :p

This is Fernando's terrain

So you want a superb paella... I've the restaurant for you: Tapelia .

Good ambience, good service, incredible paella (and other rices recipes as arroz abanda, arroz negro, arroz con bogavante or arroz con verduras), other good recipes, and a not super-expensive price (about 25-30 € per person, two courses, red wine and dessert).

The bad thing about Madrid is that our typical recipes are not very good. The good thing is that you can find the best spanish recipes concentrated in one city Just ask for something you would like to taste

Fernando