A sujihiki would probably be a good all around option for sushi and just about anything else.
Maybe a Richmond Artifex suji to start with: http://www.chefknivestogo.com/riar27su.html
I'm sure there are better ones for more money that others will recommend, but for the money the Artifex is one that I am looking at getting myself. A nice thin and flexible blade without being flimsy, and made of AEB-L steel which is a fine grain stainless made for razor blades. It should take a very nice edge very easily and hold it well for home use.
A gyuto might work fine, but I'm thinking the narrower blade profile and thin, narrow tip of a suji might be better for fish without being purpose built for fish like a yanagiba.