Okay, before trying to do anything, note down all HMs in the game.
In Pokemon Platinum, the HMs are:
Cut - Roserade, Infernape
Surf - Rampardos
Fly
Strength - Rampardos, Infernape
Defog
Rock Smash - Rampardos, Infernape
Waterfall
Rock Climb - Rampardos, Infernape
Now, out of your three Pokemon, they can all learn the unboldened moves.
Fly, Defog and Waterfall will need to be handled in you next three Pokemon.
Our main priority is Fly however. Defog and Waterfall are rarely used in the game, but you will need them at some point.
Now for types. You have Fire, Grass and Steel. I'd rather dropping Roserade from your party (Grass can be pretty useless throughout the game, especially considering you have now beaten Wake. However, Grass can be very helpful on some notes)
Good types you can add to your party that will be helpful are:
Electric, Water/Ice, Ghost/Psychic, Flying (possibly)
Electric is great, and I strongly recommend you have it. Of course, Earthquake will quickly demolish the Pokemon when you come to the Elite Four, but excluding that it's really helpful. Two of my recommendations are Pikachu and Luxray. Both can learn very good moves. You can get a Shinx around the place pretty simply, and Pikachu can be found in the Mansion's Garden near Hearthome. You could also try Magnezone if you want, however two Steel Pokemon wouldn't look good.
Since you have Surf covered, you can choose between Ice and Water. (Assuming you don't want a Pokemon that knows Waterfall. I'd recommend not though) My strongest recommendation for Ice is Mamoswine. Of course, Speed is 80 is okay. However, it's over-the-roof (or, at least 'high') Attack stat makes up for it. You could also combine Ice and Flying with Delibird, though it has the rubbish-of-rubbish stats. (75 Speed, highest stat) you can try your luck with it I guess. As for Water, I'm not going to very in-depth but my recommendations are Gyarados (Water Flying, nice combo. All around Sinnoh) and I would strongly recommend Milotic as well. (If you're brave enough, you could try the GTS and all, but quite frankly if you can't find it, you can't find it. Mt. Coronet.) Good stats. Also, try Pelipper. Another Water-Flying one, with good stats.
If you have space try your luck with Ghost/Psychic. Gallade is just plain awesome, with really high stats, and also with it being Fighting, you won't go wrong. Find a Ralts at Route 208 and 209. Along with Spiritomb, which is the only available Pokemon in the game that has no weaknesses. It will be hard to find a Sableye, so I'd strongly recommend that. Also, one of my major strong recommendations are Drifblim. Drifblim can learn Fly and Defog and is Ghost and Flying. Stats are useless, but take it from someone who has played the game with it. Trust me, if you train it correctly you will thank me for doing this.
I've suggested my Flying-types I'm sure.
Also, I would strongly recommend you learn only useful HMs like Strength, Fly, Surf
and Rock Smash. If you have to learn these moves, feel free to. Just know that Canalave City is near, the Move Deleter's city. :)
Sorry about the wall of text. xD
Good Luck! :D
