Here are the list of fishes by size, which may be helpful when selecting a bait:
Small
Kissing Gourami - no bait listed, required level 3
Tetra - no bait listed, no required level
Red Tailed Shark - requires small fish bait, required level 5
Pirahna - requires medium fish bait, required level 5
Perch - no bait listed, no required level
Minnow - no bait listed, no required level
Guppy - no bait listed, no required level
Betta - no bait listed, required level 3
Angelfish - no bait listed, required level 3
Goldfish - no bait listed no required level
Medium
Treefish - no bait listed, no required level
Batfish - no bait listed, no required level
Trout - no bait listed, required level 2
Tilapia - no bait listed, required level 4
Rainbow Fish - required bait disabled, required level 6
Koi - no bait listed, required level 2
Catfish - requires organic bait, required level 4
Bass - no bait listed, requires level 2
Anglerfish - requires medium fish bait, required level 7
Large
Salmon - no bait listed, requires level 3
Wolf Eel - requires frog bait, required level 5
Sturgeon - no bait listed, requires level 7
There are also modifier values assigned to baits, but I don't know whether they modify effective skill level, fish size or fish value in some other way. If it matters, then medium fish would be the best fish to use as bait as it has the highest modifier of 3, trash has a modifier of -2 being the worst.