Treecko-he's your starter as you said, so he's found in the beginning obviously.
Whismur-Found in Route 106, Desert Underpass, Rusturf Tunnel, Victory Road. He can be obtained pretty early.
Grimer-He's found in the fiery path, but he's still pretty rare.
Trapinch-Found in Route 111 (Desert) and the Mirage Tower.
Makuhita-Found in Granite Cave Floor 1 & Basement 1, Victory Road Floor.
Vulpix-Found at Mt. Pyre in the Grass. This one will take some time to get to.
Corphish-Found on Routes 102 & 117, Petalburg City (Fish)
Vulpix will probably take the longest to get.