I have visited Barcelona some twelve or thirteen times, so I will make some recommendations for Danielle and anyone else interested. I am going again at the beginning of February, and hopefully some good tips will get posted on this thread in the meantime.
My strong view is that, although Barcelona has some good restaurants, it is a better city for casual eating/tapas and food shopping than fine dining.
Bux is absolutely right about the wonderful food markets, such as La Boqueria. Extra tip: not only are there good casual restaurants around the perimeters of the markets, there also tend to be bars right inside. Choose a good location, climb up on a stool, and you have a drink and a slice of tortilla while watching the extraordinary shopping rituals in comfort. Free (or cheap) show for foodies.
The restaurants which always get listed in the tourist guides are predictable, okay-ish, but not the best the city has to offer. Examples: Amaya, Los Caracoles, Agut d'Avinyon, and Gambrinus. I haven't been to the famous fish restaurant Botafumeiro. Set Portes is an honourable exception; a landmark restaurant, it is now heavily used by tourists (but still by locals too). It is scattered with memorabilia and promotional gimmicks, but I have always found the food to be fine. The paellas are famous, but I also recommend their simple meat dishes - roast, kid and roast rabbit especially.
If it is your first visit, don't plan on having dinner much before ten o'clock. Sure, you'll easily get a table before ten, but you'll be eating either by yourselves or with tourists. The locals get very busy between about eleven at night and three in the morning (or later).
Locals are used to eating a number of tapas, then going off to dinner. My preference was to alternate: spend some evenings eating tapas freely, reserving other evenings for restuarant experiences.
What else? Non-violent petty crime is back in bucketloads. Keep all valuables concealed, and don't let yourselves be surrounded by gypsy flower sellers or any other odd-looking groups. I should emphasise, that I have always found it a safe city when it comes to personal safety, and will walk most areas at night without hesitation. The Barri Xines (Barrio Chino) is an exception. Go by all means, but make sure you know where you're going and don't hang around.
Specific recommendations you might not pick up from guides:
One of my favorite restaurants in the world is Ateneu Gastronomic (http://www.ateneu.com/index22.html). Carefully sourced local produce, obsessive recreation of Catalunyan cuisine, superb (and cheap) local wines. Restaurants in Spain barely mark up their wines, meaning you can often pick from the best on the list for the equivalent of around ฮ or ุ.
For tapas, the nearer you are to the Ramblas (and indeed the Plaza del Rey), the more expensive and less interesting the tapas will generally be. Walking south from the Plaza de Catalunya, there's a big seafood tapas bar on your right; it's pricy, but the quality is high. Search the side streets or the less-touristed parts of town; it's easy to get an idea of the selection by peering through the window.
I recommend El Portalon if you can find it (anyone - let me know if you're really interested, and I'll hunt down the address). It's an old-style bar, deep in the Barri Gotic. In addition to cheap, rough wine straight from the barrel, they serve tasty, authentic tapas: snails, deep-fried artichoke hearts, blood sausage, cuttlefish, as well as all the usual suspects. They also serve the Catalunyan version of paella, known as fideu, with vermicelli replacing the rice.
El Xampanyet is indeed in the guides, but is worth singling out. Get there at opening time if you can (around 6.30/7) not just to drink the local artisanal cider (which is okay) or cava (which is distressingly sweet) but to eat the delicious little open sandwiches which are spread out on the bar (catalan sausage; tuna and pimento; anchovy; tortilla; etc) or order canned seafood tapas. I am not joking - they have every kind of wonderful little sea thing canned in oil, from sardines and anchovies to baby squid and cockles.
If you're drinking, don't miss Bar Pastis on Carrer Santa Monica. Go late for a digestif, and run the bizarre (but essentially unthreatening) gauntlet of over-sized transvestite prostitutes before diving gratefully through the door of this tiny, 1940s-style French bar. Piaf, Trenet, Ricard - you get the picture.
What I am looking for, if anyone can help, is suggestions for good restaurants which are not on the regular tourist track. Thanks in advance.