PPs suggestions are all excellent. Depending on what type of cuisine you enjoy, you might also consider the following (which are fairly easy to get into without reservations, so you can make a game time decision):
Seafood: Fulton's at Downtown -- you can usually get seats in the lounge with no reservations, and the lounge is right on the water. It's fun and not horribly expensive. (BlueZoo at the Dolphin is great too -- but it is wicked expensive. We often eat in the lounge area at BlueZoo, small plates and drinks/wine.)
Japanese/Asian: Kimonos at the Swan has great sushi and it is a really neat place. Also a lounge, opens at 5:30, with kareoke after 9:30 so work around or with that depending on whether it's your thing. There are pictures and menu online and swandolphin.com. (Several good restaurants at swandolphin.com you check out online, including BlueZoo.)
African/Asian Fusion: Sanaa at Animal Kingdom Lodge (again, lounge means less waiting than dining room). Neat food, great atmosphere. Very fun. Animals right outside the window!
Have a great trip!