@ Black Glasses
He's useful for snatching and stalling out the opponent. Feint Attack is there so he has something to attack with.
@ Twisted Spoon/Spell Tag
Reflect because you get Earthquake spammed later on. Shadow Ball was Physical at the time, so you may want to consider Spell Tag instead.
@ Amulet Coin?
Focus Punch/Rain Dance
Magnet isn't available, so give it what you think is useful. Give it Rain Dance if you learn Thunder for better accuracy.
@ Mystic Water
You can choose between three starters early on, and I chose Croconaw. It comes with Mystic Water to boost Surf.
@ Black Belt
High Jump Kick
For a fighting-type, it's a battle between Makuhita, Meditite and Hitmontop.
Hitmontop can support with Intimidate.
Hariyama has survivability with Thick Fat.
Medicham is strong with Pure Power.
@ Soft Sand
It arrives a little later, but it quickly evolves into Flygon with the useful Levitate ability.
Tyranitar is the most powerful non-legendary in the game. Just keep in mind that Crunch was Special at the time.
Metagross has beastly stats and a great defensive typing. It has no 4x weaknesses, so it's hard to KO.
Raikou is fast and one of the best special sweepers in the game.
Suicune is hard to KO and even harder to stop once it gets rolling with Calm Mind and its high defenses.
Less fragile than other fire-types.
Focus Punch/Brick Break
Heracross isn't considered because it arrives very late in the game. Nonetheless, it is one of the most feared Pokemon and many of its counters can lose to it.