It's sort of hard for me to pinpoint my favorite because both have things about them that annoy me.
I can't stand how you have to max out Feebas's beauty just to evolve it. I really can't explain to you how frustrated I was after leveling up a Feebas past 50 thinking, "Oh it will evolve at some point." just to find out the sad truth. ;o; Although according to Serebii you can now evolve Feebas by trading it with Clean Scales? Sounds better then maxing out beauty, but I can't stand trading either. :D
The only thing that bothers me about Gyarados is the fact that it's a physical attacker. I like all my water types to be special attackers because they benefit a lot more off of Surf (a move I pretty much equip any water Pokemon with on my team) then a physical Pokemon does. Dumb reason, I know, but it still bothers me to some extent.
I guess after really thinking about it I like Milotic more. I prefer the design and the stat distribution much more so then Gyarados. It's just the whole finding a Feebas and evolving it part that's a pain.