In Explorers of the Sky, I tend to use Riolu as mine (partner varies save file to save file), and I find that the moveset is rather limiting, so you might want to find TMs, preferably ones that give a good balance of types. I like Iron tail and Shadow Claw, in addition to a fighting move (Force palm, Focus blast, etc.). However, finding these may be somewhat challenging, so it might not be the best one to start out with.
You will want to play the last two special episodes. The team Charm one doesn't seem as impressing as it actually is, but you will now what I mean when you finish it (it is better than the Sunfora one), but you will one to finish the very last one.