I've been living in Marseille for the past two months, and as I've seen the recommendations on this board tend to repeat each other, and are also geared towards the more michelin-starred type places, I thought I'd add my two cents, since I'm on a chowbudget.
I live right by the Vieux Port, which is, as people say, dominated by tourist-friendly restaurants serving unexceptional food (the exception might be the very famous le Miramar, which is very expensive). But! A great place to check out just a few steps up on the southern bank is Rue Sainte. There's a great, casual wine bar called 'La Part des Anges' which serves great food, and has been shaking up the low-key culinary marseillais culinary scene recently. It's also one of the few places you can get a decent glass of wine, as opposed to a bottle. Also just a good wine store in general, very friendly owner.
For the even more budget minded, down the street is 'L'Ambassade de Bretagne' which is cheap and great, serves crepes but also has daily specials according to the season. A notch up in prices from La Part is l'Aromat', supposed to be great, I'm meaning to check it out.
If you go a little farther out, to the Cours Julien and La Plaine, there's a ton of great places to grab a beer and hang out. It's the young and cool place in Marseille. The other night I went to a tapas place called 'La Cercle Rouge' which was really good, we had like three tapas each and a few bottles of wine, came to 30 euro each. There's a cafe at Cours Julien called l'Equitable, it's a type of coop café, they also have fresh produce sometimes, you have to buy a membership (it's like a euro), but great hippie crowd. Another sweet bar is Au Petit Nice, at La Plaine.
That reminds me - there's the Marché des Paysans (farmer's market) every wednesday morning in the cours julien - way better stuff than you'll find at Noailles (ie organic). You can find all types of terrines, exotic eggs, confitures à la maison, eggs, juices as well. The other organic supermarket I've found is called the 'biocoop' or something like that, the address if 87 rue de l'Italie.
I also checked out 'Le Côte de Boeuf' which famously has the 'best' - or at least the oldest - cave (wine cellar) in Marseille. If you're in Marseille and you don't like fish, it's a step away from the Vieux Port and very intimate. The meat (steeaaak!) is definitely up to par, la moêle (bone marrow) was delicious. More expensive though for sure.
A few cafés that I'd like to give shout outs to - Café de la Banque, around the corner from the American embassy and the Préfécture, serves decent food and great coffee. Probably my favorite parisian style brasserie so far. While you're in town a nice little quarter to explore is the Panier, just above the Northern bank of the Vieux Port. There's a cute little café called 'Cup of Tea' overlooking a very picturesque square, a really great salon du thé, more for the tea lovers out there obviously, but nice for the location as well. Around the corner from there is a store called 'Places aux Huiles' where you can buy some nice AOC olive oil to bring back home.
For drinks at night, I also like Bar de la Marine on the port, it's a very old, famous bar, the setting for some Marcel Pagnol films. It even has it's own wikipedia page (in French)! You can drink outside on the port, in my opinion the best place for a drink when the weather suits. Make sure to try the city's specialty, Pastis.
And of course if you're in Marseille you've got to stop at La Samaritaine for a café, great historic spot, very Marseille. Another café by the opéra is Cafés Débout, which serves great coffée, a cut above. Not the best view however.
Someone else mentioned Sylvain Depuichaffray, amazing creative patisserie that makes these great green tea/rasberry tarts, they also have new creations everyday. For more traditional pastries, across from the Opéra is 'le Pain de l'Opera' which has great tarts, sandwiches, cakes, everything really. Macarons!
For great chocolate there's always the classic Puyricard - the chocolates are the same as you'll get in Aix. I REALLY have been meaning to go to this place called Xocoatl which has more creative/modern/international style chocolate. The other Marseille specialty you should get while in town are called 'navettes,' you can get them at more boulangeries, but if you want them straight out of the oven head up Rue Sainte to Les Fours des Navettes - it actually predates the French revolution. Buy a few, I prefer them when they're warm straight out of the oven. They're essentially long skinny sort of crunchy biscuits, not very sweet, but made with a flavor of fleur d'oranger, essentially the flowers from a bitter orange tree. I don't like orange even but I love these biscuits.
Oh and finally this has been mentioned to death, but there's the fish market every morning in front of the Vieux Port, from around 8 until 1pm, though I would suggest getting there before 10am if possible, that's when the fish are the freshest.
If someone knows of something great that I'm missing - and that won't break the bank - let me know! I've been meaning to check out La Lauracée close to where I live (close the Sylvain), but it's kind of expensive. Supposed to be really good though, Provencal style bistro food. Also of course Le Petit Nice Passédat, Café des Épices, l'Epuisette... but those are malheureusement kind of out of my price range. I'm probably forgetting some great stuff I've tried as well. If you're coming though I might reconsider if I can find someone game! My roommates are also all poor students.
Non-food type stuff that you should do in Marseille: walk from the Vieux Port along the Corniche to the Parc Borély. A bit of a hike but definitely worth it, the best scenery doesn't start until you pass the little cluster of bars and shops jutting out around Le Petit Nice Passédat (the famous three star Michelin place). Actually, a great thing to do (that's free!) is to go down towards the restaurant, and then turn right towards this little overlook, and bring a little picnic basket out onto the rocks overlooking the ocean from there. There's always a nice little crowd of French sun worshippers hanging out at that spot. Message me if those directions were not clear enough - it's really the best place to enjoy a nice day in Marseille in my opinion.
I would suggest also this useful little guide (in French) for all of Provence:
The French version of Yelp/Chowhound is cityvox.fr, also very helpful and obviously always up to date. French Elle also has a nice city guide for restuarants, food stores, everything:
If people find this helpful, I can also post some things I've found in Aix en Provence, as I've been heading up there pretty frequently as well. By the way if you're heading to Aix out of Marseille, take the bus not the train. It's like 20 min versus an hour.