Magnezone is an awesome alternative to the sheep line. It's steel/electric though, which makes it vulnerable to fire/ground by 4X!
Still, it has higher defenses (it loses static though), higher sp attack, and slight higher speed. Despite losing resistance to ground, fighting and fire, it also gains from bug, psychic, ghost and a couple more... including dragon! It can learn quite a few more moves as well. Magnemite can be found at Virbank Complex., but you need to train Magneton at Chargestone Cave.
Crobat is pretty sturdy. It's fast, it's quite powerful and can take some hits as well. Raising it can be a pain, but it will be worth. Zubats are ubiquitous at Castelia Sewers.
Haxorus is a mammoth. With dragon dance + outrage + earthquake, nothing can stand in their way. You can get an Axew in Mistralton Cave.
Flygon is another alternative if you don't like Haxorus. It lacks some stats and has a 4X weakness to ice, but it is more well-rounded. The sp atk is quite similar to the attack. Trapinch can be found in Desert Resort outside the complex, but it is VERY RARE.
Lucario is one of the best. Steel + fighting resists plenty of hits and moves. Quite weak in defenses, but pretty solid in attack and sp atk. Speed is decent. Riolu can be found in Flossey Farm, but it is VERY RARE.
There are a couple more: Starmie, Lapras, Hyderigon, Chandelure, Metagross etc. which I'm lazy to mention. I hope you don't mind any spelling mistakes.