To me by far the best one is Ong Shun seafood restaurant at Johor bahru. Food is slightly above average but i like it because their small size dishes equivalent to typical medium portion here in KL. Their sweet potato leaves stir fry with sambal is my must have dish. Quite a famous place for dining and got frequent customers of all races.

I stay at klang valley too but i travel to JB a lot. Im not dare to suggest any because all seafood restaurants in klang valley more or less the same. However, just in case if you ever drop by JB then give it a try.