Some must-try foods in New Orleans are Po-boy, fried seafood, blackened redfish, Vietnamese Gumbo, and more.