There used to be many of these places in Bucharest and generally in the country. Unfortunately there are fewer and fewer. Called "berărie" or "terasă", they used to provide a great, warm atmosphere where regular people used to meet, eat some mici and pickles, drink draft beer in the smoke created by the grill where they cooked the mici. Then they used to debate forever over the eternal topics: politics, women and soccer. There were just a few options and there used to be no menu (or the menu was just a piece of paper in the window). Nowadays there are not so many places like that in the old quarter and I think these too will disappear soon. Actually they are next to extinct in the central area.
So, for the mici lovers, one can find them in a few traditional restaurants; the mici at Vatra Restaurant are especially recommended. Otherwise, all Bucharestians used to know La Cocoșatu', a place that started with a berărie just to end with a big restaurant (currently closed, with the business overtaken by La Gil nearby). They had their own butcher shop, preparing the mici meat themselves, located on Str. Neagoe Vodă nr. 52A, near Bucharest Băneasa Airport; the La Gil followed more or less the same recipe. For the traditional / simple way of serving the mici (i.e. with mustard and pickles while standing, in an air filled with the smoke coming from the grill), one can take the subway to 1 Mai or bus #300 to the end of the line and look for the Gerard / Piața Chibrit sign (or just for the smoke).
What to recommend when it comes to the mici? What else but the mici (minced pork and mutton, mixed with garlic and spices, then grilled and served with mustard), the pickles coming from a large jar, and the draft beer. For there usually is not much more than that anyway. And no need for anything else.
The mici (also referred to as mititei) themselves (or variations) can be found all over the Balkans and in the Middle East. They are known as ćevapčići (or just ćevapi) in Serbia, Croatia, Montenegro and Bosnia (served with onions instead of mustard and, the farther one goes South or East, they get smaller and are made of mutton only). One can find the kebapche in Bulgaria (the biggest of the bunch, made of beef and pork usually). In Macedonia one has the ćebapi and in Slovenia the čevapčiči. They all come from the Arab kebap that arrived in this area with the Turks, disregarding of the popular story that mentions a cook at Manuc Inn which, smashing a meatball by mistake, created the first mic. But never mind all this theory, just go out and enjoy some mici.
GPS - Vatra Restaurant - N44 26.131 E26 05.678
GPS - La Gil - N44 29.655 E26 04.991
GPS - Gerard - N44 28.270 E26 03.121