I just recalled:
Darius Gaiden (Saturn)
It's a side-scroller with bosses that are huge flying fish. There are a few levels that you submerge and have a nice tough time beating it.