Definately Wintzell's, but be sure to go to the original one in the historic section of downtown Mobile, Dauphine St. It's been there for as long as I can remember. It will give you a true taste and feel of the South.
I guess you can use your imagination about what the south tastes like...
As a native Mobilian, I would suggest lesser-known restaraunts that are OUTSTANDING. For Italian, try La Pizzeria in the historic Leinkauf District or Guido's/Cousin Vinny's near Washington Square.
For seafood - Guido's is also good and has a more exotic menu than Wintzell's. I used to work a block away from Wintzell's, so I ate there more than I wanted to, but there is nothing really great on their menu except 25-cent oysters and homemade gumbo.
For Mexican - Try El Giro's on Government Street (Hwy 90)...Two words -DOLLAR MARGARITAS.
Sightseeing - Battleship/Bellingrath is fun the first time - or just wander around and look through everybody's giant windows in midtown - you never know what you might see~!