If you're in Recoleta, one place you should try is El Cuartito ("the small room") at Talcahuano 937. When I was staying in that area, some local friends took me there, saying it's the best pizza place in the world. (They're rather serious about it too.) The place has been serving pizza since 1934, and while no longer just a small room (having been extended a few times), I believe the atmosphere and popularity is pretty much unchanged from those years.
Photos by yours truly
Most pizzas were ~ 30-70 $AR (April 2011). Quite different from pizza I'd had before, but great!
Of course, BA is full of really nice restaurants that still aren't "super fancy". In most places above all the beef dishes are great (it's Argentina, after all), and everything's very affordable taking the quality into account (well, at least if you're coming from Europe). I'll see if I find some notes of mine so I could name a few more restaurants...