I would say get Abra.
It has great special attack especially when it evolves and good speed which is what you want when you play through a game. It is also easy to find. It can be a little bit hard to catch since it always teleports away at turn 1, but every time you fight it you get the chance to throw a pokéball and there is a 24,5% chance to catch it at full HP with a pokéball so you'll get it after approximately 5 tries.
There is one more thing that is difficult with Abra and that is that it doesn't learn any moves untill it evolves so keep that in mind. It can learn several TMs though.
You can find Abra at Route 203, 215. Route 203 is pretty early in the game.
If you want another Pokémon I would say Meditite.
While it doesn't have the best stats it does have the ability Pure Power. Which raises it's attack. I like the typing of this pokémon which is Psychic/Fighting. If you find some Heart Scales you can learn it Zen Headbutt when it has evolved to Medicham which also has the ability Pure Power. It isn't as strong as Alakazam but it is another Pokémon which is easy to find in Platinum.
You can find it at Route 210, 211, 216, Mt. Coronet
//Jofly
