Tentacruel, no contest. It's extremely difficult to fish up a Feebas, let alone evolve it. It'll waste time when you could be playing the game so much faster. Tentacruel, on the other hand, can be found easily on most water routes. It's fast, and has a very good Special Defense stat. It can learn Cut, Surf, Dive, and Waterfall, making it an exceptional HM slave.
Tentacruel is very clearly the winner, due to ease of access and the HMs it can learn.
Hope I helped!