Starfish in Thorndon is pretty good, but very expensive.
Aro Fish in Aro Street is quite popular, but mainly with students who have no taste (/jk) - I find them a bit hit & miss but mostly pretty good.
Paradise Seafoods in Kelburn is decidedly average.
Brooklyn fish supply is marginally above average, depends who is running the show at the time.
Bond Street apparently does a pretty good chinese meal, I haven't tried the fish & chips under the current management but they used to be ok. They did tend to run the oil a bit old though.
The shop out by Hutt Raceway that won the awards a couple of years running about 5 years back is a bit over-rated, but still pretty good.
Wellington Trawling sea market (the one at the top of Cuba St) - excellent fish, terrible chips. Their Lambton Quay branch is better, but nothing exciting.
Agree with Mauricio, the old shop in Johnsonville is pretty bleak. The one attached to the Mall is better but still nothing very exciting.
I like a good fish & chips :)