I need a game-beating team in Explorers of Sky!

Hello everyone. I've been obsessed with Mystery Dungeon lately (as well as ACNL XD) to the point that I started a walkthrough of Sky on my youtube channel (/user/LetheTheRaptor). Anyway, the only time I've gotten to the very end and beaten Darkrai was the first time I actually played Sky (Hero: Piplup/Empoleon, Partner: Pikachu/Raichu).

Anyway, I wanted to play the game again and hastily deleted my save. A lot of my friends have played the game but never got to Darkrai, of which I was very proud of that fact. My question is, what's a good team to get through the game. My favorite pokemon is Umbreon, and I've tried playing as eevee before and it was pretty good. I got tired of only tackle, so I used wondermail generators to get Dig and Shadow Ball. My partner was a Vulpix which I though would support Umbreon very well (IE: Extrasensory for fighting, Fire moves for bug). I liked that team, but only got past the future before I stopped. I feel that Vulpix is too over-used (Two of my friends used Vulpix/Riolu and Riolu/Vulpix so it felt weird to use such a common pokemon among my friends).

So my question is this, I want to be able to beat Darkrai in a few weeks at latest. My family is going on a road trip soon, so I can play the heck out of my game. What's a good partner for Eevee/Umbreon. I'd like a pokemon with enough bulk to support eevee, and then be able to support an Umbreon as well. I tried Torchic once, as Blazikin gets Brave bird, Fire moves as well as Fighting. I'd also like movesets if possible, for eevee then when I evolve (I definitely want Moonlight and Assurance) and a moveset for my partner. Any recruited pokemon would be nice too, but not required. Thank you guys and sorry this is so very long!

EDIT: My favorite types are Dark Obviously), grass and flying. Since there is no Grass/Flying starter I'm thinking Grass or Fire. I'm now thinking Charmander would be good, as when he evolves he gets Heat Wave and gains the flying type. I'll add a poll to vote for which partner my eevee/umbreon should have!

EDIT 2: Messed up the poll... Don't vote for any normal types as I can't be partnered with them...

FINAL EDIT: I decided to go with Vulpix once again.

EDIT: 4: I'm getting opinions about Riolu. The only problem is they are both weak to Fighting when evolved.

Yeah, I just feel Riolu is very overdone. I might switch out to a Riolu (i'm only at the Apple Woods) though as I think he might be beter with Umbreon. Thanks for your opinion.

EDIT: The only problem is that when they both evolve they will both be weak to Fighting...

maybe you should keep that easier for dialga anyway if not get cyndaquil maybe pikachu I chose pikachu and riolu my first playthrough of sky I did pretty good.

Here I was thinking Turtwig and other grass pokemon were "easy" because of absorb and mega-drain. I started out with a Turtwig and Vulpix, and got through the game pretty well; I did have a few accidents here and there though u,u'

Also, I will say that Chansey and Blissey really come through in this game n,n (Post game though :/ )

Try Turtwig. They are very reliable in the main games and reliable in Mystery Dungeon. As a second option, I suggest Piplup or maybe Bulbasaur.

Thanks guys! I made Turtwgi my hero once because he's my fave starter, but I don't like that he can't use Earthquake effectively without hurting my allies. Like I said I beat the game with Piplup so I really love that guy. Dark/Water/Steel seems pretty good for evolution. Hmm. I could always use Wonder Mail to recruit other pokemon I want. I think that Umbreon, Lucario, Blissey and another pokemon for my team? I had an egg-hatched numel which was epic with Earth Power! I'm now thinking Piplup since it can have Water Pulse (Ranged), Blizzard (Entire Room), Flash Cannon (Ranged, Evolved), Peck? (PP Move, Coverage). Umbreon could have Moonlight (Entire Party Healing), Dark Pulse (All Arounder), Shadow Ball (range), maybe Psychic? I could also recruit Lucario! Aura Sphere (Baws ranged), Dark Pulse (All arounder), Flash Cannon (Range), Detect? I need a 4th member. I'm thinking Sky-Forme Shaymin! Energy Ball (Range), Air Slash, Seed Flare, Sweet Kiss/Quick Attack/Filler. I think I'll use this team! Thanks!

Meowth would make an extroidinary partner for you! I use him all the time in my SKy playthroughs. He is extremely powerful with Technician, meaning moves like Bite will do a lot more damage than they usually do. He learns a wide variety of moves with TMs and can cause flinch status and hit from a distance with Fake Out. Also, Pick Up is always a good thing.