As for rectilinear vs. fisheye - it is really a question of taste - even underwater. Yes, the lack of straight sharp "horizons" lacking in many underwater photos makes the fisheye distortion less noticable - and the bottom/watercolums "horizon" curvature is often seen as just a natural "slope". However, some people really do NOT like the fisheye look. I am one of those and I find the fisheye distortion very unattractive. I have fellow shooters who have absolutely no problem with images with fisheye distortion and even consider it attractive. So there you go, you have to decide if it rubs you the right or the wrong way. And do also remeber that the rectilinear Canon Ef-s 10-22mm will give you distortion as well, it just doesn't give you the round bulging FE convex distortion.
If you are not a fan of Fish Eye then the rectilinear Canon 10-22mmm is really a reasonable choise, especially if you consider the alternative of the much more expensive rectilinear Canon 14mm prime. You get the ability to focus extremely close, and you have the flexibility to zoom all the way to 22mm which is great when that dolphin just won't let you any closer...
Yes at 10mm the corners can be a bit soft, and if that is really truly something that bothers you, then beware. I personally never lost any sleep over soft corners and am somewhat amused at all the attention this particular issue always gets. As I see it, for one, due to composition, expecially CFWA, most "corners" contains either blue water or some bottom substrate that is not part of the subject. Secondly, although shooting at 10mm is nice, I seldom find myself shooting all the way at 10mm.
If I could justify it, I would go with the rectilinear 14mm, but the 10-22 is a pretty darn good alternative.
The downside to this lens is that it has the EF-S mount if you are going to shoot a full frame one day.
I personally think this is a really funpacked lens and I just can't get enough of it both over and under the surface.