Pokemon
¤ Red and Blue
¤ Red and Green (Japanese)
¤ Blue Version (Japanese)
¤ Yellow Version
¤ Gold and Silver
¤ Crystal Version
¤ Ruby and Sapphire
¤ Emerald Version
¤ FireRed & LeafGreen
¤ Diamond and Pearl
¤ Platinum Version

Universal Information
¤ What is this section?
¤ Breeding Pokemon
¤ Elemental Types
¤ Pokerus Infection
¤ Shiny Pokemon

Affiliates
¤ Amity Square
¤ Dark Eon Hideout
¤ Eevee's Headquarters
¤ Jenviousity
¤ Lugia's Island
¤ Perfect Absolution
¤ Pokemon Inferno
¤ Pokeshore
¤ PokeTech
¤ Pokeuniverse
¤ Pokemon Valley
¤ Sapphire Milotic
¤ The Spriting Shack

I recommend doing the following. Grab a Pokemon that knows both surf and waterfall, and surf up along the river in Route 119. Use Waterfall when you come to one and keep going until you are stopped. Then, from here, fish 2-3 times in each tile and work your way down. You should find him within an hour or so of doing this, depending on how fast you go or if you find a Pokemon each time. Use the Old Rod to reduce your encounters to just Magikarp and the occasional Tentacool.

When you do find Feebas, be sure to fish several more times in the same area. It will probably be around the 20-30 level range. Even at this level, it can be caught using a Poke Ball and isn't much of a threat, because, like Magikarp, they only know Splash and Tackle.

I also recommend capturing a few, at least 5. Most likely your friends won't have one, and you can use it as a trading Pokemon to gain some other rare Pokemon from your friends.

What sets Feebas apart from Magikarp is the move pool. Magikarp only learns Tackle, Splash, and Flail and so does Feebas. However, Feebas can learn TM's and HM's, so it can be used in battle. It's a bit less useless. It can also be taught several tutor moves and can have various egg moves.

I'm sure you're familar with Pokeblocks and all the sorts of things with it. Feebas needs to have its Beauty stat at the maximum (or within that blue circle) before it can evolve. When this has been met, it will evolve the next time it gains a level. It will then evolve into the stunning Milotic.