Nor-Joe's, an Italian import store in Old Metairie, has one of the best. Be sure to order the deluxe muffaletta. It contains lots of premium Italian deli meat such as proscuitto and mortadella. Other places around town sometimes skimp on the quality of the deli meats.
In the Quarter, The Napoleon House has a pretty good one though I think they use pastrami as one of the ingredients which may offend some purists.