http://www.disciplesoftheland.com/fish/#Titanic-Sawfish

This is the best guide from the best XIV fishing forum since 1.0. Click on any page then fish and you'll see which bait is optimal; it is set up identically to your fishing log. It also gives you the optimal path for the more difficult fish. For example, I've linked the page for the Titanic Sawfish; most people think using Lugworms (very low level bait) has to be a typo or something. In reality, it locks in the first fish required for the mooch chain (you can only catch Gobies with the lugworm), which actually accelerates your chances of landing a Sawfish immensely.

All credit goes to Kida on that forum; he is part fish.