Breloom
Followed by Heracross, and then Gallade.
Shroomish is found very early on, and evolves as soon as level 23 where it learns Mach Punch which helps offset its relative lack of speed. (Note that it's still fast enough for most of your opponents provided you are sufficiently levelled up). From there it learns Force Palm and Sky Uppercut, both excellent moves. It can also learn Spore/Stun Spore and False Swipe for late game legendary Pokémon catching. It's also useful for the HMs Cut and Strength.
If you're willing to wait till Safari Zone, then Heracross is another good alternative. It learns Brick Break naturally at level 28 and the super powerful Close Combat at 43. It's also useful for Strength and Rock Smash, should you need it.
Finally, you can also try out Gallade, but you'll need the TM for Brick Break or the move tutor for Drain Punch for it to be a potent fighting type sweeper. And also wait till you get a Dawn Stone. Personally, I prefer getting a Gardevoir over Gallade but if you're willing to try something new then this is a fine alternative.