I think an amazing teammate for Fox is Little Mac. This isn't just me theorycrafting Mac+X in dubs, I've done this team to surprisingly grear success.
+
I did this team with Frupcakes this past weekend at Enthusiast Gaming Live (Toryuken 4) up here in Ontario. We got 7th place in a very stacked tournament.
So all of us know that I used to beatch about Mac until I got better and noticed how the stage list hates him because he suffers from having a "For Glory" design which screws him in singles every time high platforms are involved. In doubles tho, this weakness is negligible with a teammate to cover it, and I think Fox is one of those amazing teammates with his fast falling speed and ground speed letting him help and cover the places Mac can't. Because of the nature of dubs, opponents are also forced to deal with Little Mac instead of camping him out, unlike in singles where he can be counterpicked relatively easily.
Both of these characters have really good synergy with each other, despite both of them preferring to stay on-stage. The general gameplan is to let Mac engage while you as Fox follow closely behind him, waiting for openings that Little Mac creates which Fox is very good at capitalizing on. Little Mac is very good at engaging in 2v1s thanks to super-armour and fast moves, but Mac being Mac also means he gets tossed offstage and dies.
For this team to work, Fox and Mac stick close together as much as possible while they focus on dividing their opponents and harassing them, helping each other out when one of them gets in trouble. You want to be at a distance where the other one can get there and knock one of the opponents away while still respecting Mac's range to avoid friendly fire. Played right, you have two fast characters that can separate opposing teammates relatively well and create openings for each other.
What Fox brings to the table for Mac:
1. He's really good at separating the opposite team. Should Mac start to get overwhelmed, Fox can help him very quickly and toss an opponent away from him, since his attacks come out so fast.
2. Fox is really good at applying pressure below platforms. Since Little Mac has no air presence, Fox covering them removes Mac's weakness. (Of course, if only one opponent runs to a platform and leaves his teammate, then just sandwich the teammate, which is very easy with how fast both characters are).
3. Good ways of getting a grab, whether it's through conditioning shield or getting a pivot grab on a distracted opponent. Getting a grab is essentially a free sweetspotted U-smash, F-smash or KO punch for Little Mac. This also removes Fox weakness of having no KO throw or guaranteed setup from a throw. Great for ending the 2v1 when you're in the advantage.
What Mac brings for Fox:
1. High KO power, which combined with the many ways Fox has of building damage let's Little Mac get as many KOs as possible.
2. Any opponent that gets knocked in the air by Little Mac, Fox can capitalize on them with aerials for the KO or damage.
3. The KO punch. Such a silly move, so easy to set up when you can be Fox and grab your opponent or set it up for Mac.
Essentially Little Mac's role is to make the ground a deathzone in doubles: it's his bubble, he controls that space and anyone who gets near him gets knocked away. Fox's role is to cover the places Little Mac can't reach, mainly platforms, and catch opponents that get sent flying by Mac.