Medicham is absolutely the way to go. Fighting is a useful type in-game, and it's pretty easy to get a Meditite. By contrast, Mamoswine requires a Move Relearner and a Heart Scale, and Spiritomb is a complete chore to get. Both Mamoswine and Spiritomb also overlap types with existing team members (Torterra and Houndoom respectively) while Medicham is completely unique. It doesn't get too many moves, but that's okay --- all you really need is Hi Jump Kick. Pure Power is an incredible Ability as well.
Medicham
Ability: Pure Power
- Hi Jump Kick
- Zen Headbutt / Psychic / anything
- Strength
- (filler)
Your second choice doesn't really matter. Neither of Mamoswine and Spiritomb are at all optimal to use, so just use something else that's easier to get. I personally like Floatzel, as its physical movepool complements its high Attack and Speed; it also learns important HMs like Surf that you lack otherwise.
Floatzel
Ability: Swift Swim
- Waterfall / Surf
- Ice Fang
- Aqua Jet
- Crunch
Hope I helped!