Medicham is absolutely the way to go. Fighting is a very helpful type in-game, and it's actually pretty easy to get a Meditite. On the other hand, Mamoswine requires a Move Relearner and a Heart Scale, and Spiritomb is a complete chore to get. Mamoswine also overlaps types with Torterra, and Spiritomb with Houndoom, 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)
As for your second choice, it doesn't really matter. Neither of Mamoswine and Spiritomb are at all optimal to use, so just use something else, preferably easier to get. I personally like Floatzel, as it can learn things like Waterfall, and it's very fast and strong.
Floatzel
Ability: Swift Swim
- Waterfall / Surf
- Ice Fang
- Aqua Jet
- Crunch
Hope I helped!