V&A is the ultimate dining experience and we've loved every meal there.
If they don't want to go that "fine", I think Flying Fish at the Boardwalk has the best fish/steak menu.
If they just want fish, then I would definitely suggest Todd English' bluezoo at the Dolphin. It's not Disney owned/operated and has a different clientele, much more adult and excellent, excellent food. The menu is almost all fish/seafood though.