If you're going to get a Hurricane, get the real deal at Pat O'Briens (sit on the patio). You also should make it to Café Beignet for breakfast at least once (get a coffee and a Beignet). If you're with a group, getting a King Cake could be fun (that's traditionally Mardi Gras faire, but I'm fairly sure you can find it any time). The traditional dishes are Mud Bugs, Jambalaya, Gumbo, Blackened Catfish and Red Beans and Rice. There are more restaurants worth going to than one could possibly list (http://www.neworleansrestaurants.com/index.php). Lots of famous chefs came from New Orleans and still have restaurants in the French Quarter, including Emeril Lagasse (http://www.neworleansonline.com/neworleans/cuisine/chefs/). Some of the best places I've been to there are hole in the wall places only the natives would know about. If you do ask some natives, be aware that any place that takes you to the other side of Lake Pontchatrain will require a good hour or more travel time, both ways.
Po Boy's and Muffaletta's are basically subs, and you'll find places that sell these literally on every block. Heck, some of the gas stations sell them. Yes, they are traditional and there are some really good ones, but unless you've got a lot of spare time and have a native available to take you to their favorite shop, I don't think it would be worth seeking these out.
You'll want to save some time to walk Bourbon Street, but be sure you know where to stay there. To far in either direction and you get into some, err, interesting parts of town. Not that all of Bourbon Street couldn't be described that way, but there's a big difference between the interesting shops and the "interesting residents". It can be dangerous, especially for tourists, to stray off of the main parts of Bourbon Street.
If you're there for an extended stay, a swamp boat tour is worth the price, but you'll really need a full free day for stuff like that.