My starter was Vulpix and partner Eevee. Vulpix knows a lot of special moves, and although dungeons like Waterfall Cave are tough if you don't grind, the powerful combination of moves you can put on it are excellent. I use Flamethrower +1 for range, Dark Pulse for ghosts, Faint Attack as a physical, and Toxic for bosses. I stole a Fire Stone easily with a Trawl Orb and evolved it to Ninetails as soon as I could. I have special items that make it so water heals me, and other boost items to up my stats.
For Eevee I evolved it into a Umbreon so I could teach it the nasty Psychic. I then made it learn Dark Pulse as well, and kept Bite and Quick Attack for physical attacks. It's Evolve Charm gives it EXP. and it's Dusk Collar temporarily blinds attackers. They both have over 5 IQ Stars and have high HP. Although they are only around LV. 60 right now, when they grow to 100 they will become monsters. But always remember to give them both stat boosting items, Ninetails needs extra Special Attack (and Defense/Special Defense if you can) and Umbreon needs more Defense if you want it to withstand Fighting Type moves.
TL;DR: Ninetails is good for long range (with help), and Eevee can turn into the powerhouse of a Dark Type, Umbreon (and can even have good Defense if you build it up!).